Loading...
radoslav013 avatar 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:

  1. Assign primes[0…n] = true
  2. Assign primes[0] = primes[1] = false
  3. 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
  4. Repeat for the next smallest p < n.

    http://pastebin.com/QuqyAWP5 това е моя код, ако някой ми помогне ще му бъда благодарен!
0
Programming Fundamentals
Plamen27 avatar 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();

0
ivan_danov avatar ivan_danov 4 Точки

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

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

0
Plamen27 avatar Plamen27 599 Точки

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

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

0
ZornitsaSerbezova avatar ZornitsaSerbezova 455 Точки

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

0
speednet avatar 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] + " ");
                }
            }
        }
    }
}
 

0
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.