4. Sieve of Eratosthenes

radoslav013 25 Точки

4. Sieve of Eratosthenes

Моля за малко помощ на задачата 4. Sieve of Eratosthenes от Arrays and Lists - Exercises, защото джъджа ми дава 40.

Write a program to find all prime numbers in range [1…n]. Implement the algorithm called “Sieve of Eratosthenes”: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes. Steps in the “Sieve of Eratosthenes” algorithm:

Assign primes[0…n] = true
Assign primes[0] = primes[1] = false
Find the smallest p, which holds primes[p] = true
- Print p (it is prime)
- Assign primes[2*p] = primes[3*p] = primes[4*p] = … = false
Repeat for the next smallest p < n.

http://pastebin.com/QuqyAWP5 това е моя код, ако някой ми помогне ще му бъда благодарен!

Тагове:

29/10/2016 10:07:07 Programming Fundamentals

Plamen27 599 Точки

Best Answer

Ето такъв фикс мога да ти предложа:

          int n = int.Parse(Console.ReadLine());
            bool[] A = new bool[n+1];
            for (int i = 0; i <= n; i++)
            { A[i] = true; }
            A[0] = false; A[1] = false;
            for (int i = 0; i < n+1; i++)
            {
                if (A[i])
                {
                    for (int j = 2; (j * i) <= n; j++)
                    { A[j * i] = false; }
                }
            }
             for (int j = 2; j <= n; j++)
            {
                if (A[j] == true) { Console.Write(j + " "); }
            }
            Console.WriteLine();

29/10/2016 13:55:20

ivan_danov 4 Точки

Plamen27, решението е гениално

ако сам си се сетил за него , ЕВАЛА

09/02/2018 16:56:14

Plamen27 599 Точки

Здрасти е кой друг да го е правил. Към момента когато поствах решението нямаше решение което да следва алгоритъма на ситото на Ератостен на форума. Затова постнах едно тук:

https://softuni.bg/forum/12671/4-sieve-of-eratosthenes

14/02/2018 22:06:05

ZornitsaSerbezova 455 Точки

Не виждам къде проверяваш дали числото е просто.

29/10/2016 13:07:51

speednet 12 Точки

Ето и моето решение:

using System;
using System.Linq;

namespace _04.SieveOfEratosthenes
{
class Program
{
static void Main(string[] args)
{

int n = int.Parse(Console.ReadLine());
int cur = 1, total = n;
var pc = Enumerable.Range(2, total).ToList();

while (cur <= Math.Sqrt(total))
{
cur = pc.First(i => i > cur);
pc.RemoveAll(i => i != cur && i % cur == 0);
}
if (pc.Max() > n)
{
for (int i = 0; i < pc.Count -1; i++)
{

Console.Write(pc[i] + " ");
}
}
else
{
for (int i = 0; i < pc.Count; i++)
{
Console.Write(pc[i] + " ");
}
}
}
}
}

29/01/2017 15:27:02