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

Виж всички отговори