[C#] Arrays - 15 задача


3

Условие:

15.Write a program that finds all prime numbers in the range [1...10 000 000]. Use the sieve of Eratosthenes algorithm (find it in Wikipedia).

Мое решение:

CLICK!!!




Отговори



11

Решение:

http://pastebin.com/eFch6Qe2

Обяснение:

В какво се състой този алгоритъм ? Започваме от 2 и премахваме всички числа който се делят без остатък на 2, след това вземаме следващото число 3 и премахваме всички числа който се делят на това число и т.н. до края.

Как съм го направил в задачата аз ?

1. Декларирам bool масив с 10 000 000 елемента, като индексите му отговарят на всяко число което искаме да проверим. ( по подразбиране всички елементи са false ).

2. С първия цикъл обикалям до корен квадратен от всички числа ( може да обикалята до всички числа, но така е по-бързо. Тази оптимизиаця бе показана в домашните от предишната част на курса )

3. Проверяваме дали числото е false, ако е влизаме в 2рия цикъл и го инициализираме с j = i*i със стъпка j = j + i. На всяка стъпка променяме стойността на деден елемент на true.

4. Накрая отпечатваме индексите само на тези елементи, които са false.

П.С. Алгоритъма работи, но докато сe изпише всичко на конзолата, ще пуснете 2 чифта брада :D


от Teodor92 (13062 точки)


0
Колега нз дали има смисъл от това спестяване на първия цикъл при положение, че след това в нов цикъл въртиш пак наново.

от ScorpS (1542 точки)

0
Нещо не мога да те разбера, кой цикъл спестявам ?

от Teodor92 (13062 точки)



0
Ето един опит за решение от мен с използване на List
http://pastebin.com/JS1pvg4Y
1. Добавям всичките числа от 1 до 10 000 000 в листа
2. С цикъл до корен квадратен от 10 000 000 изтривам всички елементи които не са prime
пр.
i = 2 изтривам i*2 елемента i*3 елемента докато i*x <= 10 000 000
i = 3 изтривам i*2 елемента i*3 елемента докато i*x <= 10 000 000
и т. н.
Доста е бавно обаче



0

Ето го и мойто с "List" , като обикалям всички числа, а не до кореквадратен, защото и в същото време ги печатам.

http://pastebin.com/zVux77hF

 


от ScorpS (1542 точки)


0
За да го оптимизираш, можеш да обходиш до коренквадратен като същевременно печаташ, а след това да доотпечаташ получените вече прости числа.

от konstantin.mechev (0 точки)


14

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

Вместо корен квадратен, повдигам i на квадрат за по-бързо.


от jasssonpet (6814 точки)


0
Колега решението е супер и кратко. Но загубих сигурно 2 пъти повече време да го разчета от колкото ако беше написано по четимо, не е лошо да си правим кода по-четим - в помощ може да ползваме styleCop (да не кажем че е задължително), а след като Ники спомена че трябва да минаваме домашните които проверяваме през него (както HTML през валидатора) е доста препоръчително да пишем четим и качествен код. Иначе +1 от мен.

от stoyanov (2483 точки)

0
Програма на 5 реда - какво не можеш да и разчетеш. Иначе всички уеб домашни са ми валидни. За мен четими са кратките и стегнати решения.

от jasssonpet (6814 точки)



4

 

  1. using System;
  2. using System.Collections.Generic;
  3. using System.Collections;
  4. using System.Linq;
  5. using System.Text;
  6.  
  7. class Program
  8. {
  9.     static void Main(string[] args)
  10.     {
  11.         var currentIter = 1;
  12.         int MaxRange = 10000000;
  13.         List<int> array = Enumerable.Range(2, MaxRange).ToList();
  14.  
  15.         while (currentIter <= Math.Sqrt(MaxRange))
  16.         {
  17.             int temp = currentIter;
  18.             int temp2 = pc.First(=> i > temp);
  19.             array.RemoveAll(=> i != temp2 && i % temp2 == 0);
  20.             currentIter = temp2;
  21.         }
  22.  
  23.         int[] arr = array.ToArray();
  24.         for (int i = 0; i < arr.Length; i++)
  25.         {
  26.             Console.WriteLine(arr[i]);
  27.         }
  28.     }
  29. }


    Реших да си поиграя малко, четох няколко документа, мнения,в крайна сметка стандартното решение на задачата е с корен крадратен на редицата до самото число или малко по-оптимизираният вариант(който представям).

    Имах известни проблеми със логиката, докато нагодя правилно и най-вече синтактично.

    Изчакайте 2-3 секунди докато направи сметките, тогава започва отпечатването на конзолата.

от Prophian (1234 точки)


0
Здравей, какво е това: int temp2 = pc.First(i => i > temp); От къде идва това pc.First, не мога да го намеря в интернет, VS-то не ми го разпознава....този код не ми се компилира на мен...Може ли малко хелп?

от zhelyazkovn (2949 точки)

0
Toва е linq метод -- трябва ти using System.Linq;
Ето линк : http://msdn.microsoft.com/query/dev11.query?appId=Dev11IDEF1&l=EN-US&k=k(System.Linq.Enumerable.First``1);k(TargetFrameworkMoniker-.NETFramework,Version%3Dv4.5);k(DevLang-csharp)&rd=true

от Prophian (1234 точки)


5

Привет! С малко чиста математика се опитах да оптимизирам бързодействието. Очаквам критики :)

http://pastebin.com/jiX4MGJn


от konstantin.mechev (0 точки)


2
http://pastebin.com/SBCcQPdt
Това е моето решение, предполагам ,че не е оптимално, но с две думи: -1)Заделям си масив с 10 000 000 елемента -2)Номерирам ги от 1 до 10 000 0000 -3)Всички,които се делят на 2,3,5 или 7 (без остатък) ги правя нули и от идеята на алгорутъма следва, че всички останали (по-големите от нула) са прости числа.

от boncho.vylkov (1923 точки)


0
Решението ти няма да работи коректно за числа по-големи от 100 т.к. ще отпечатваш числа, който не са кратни 2,3,5,7 но не са и прости ( 169 = 13*13 ). Виж решенията на колегите по-напред и линка в първия пост за да видиш каква е основната идея алгоритъма :)

от Teodor92 (13062 точки)

0
Колега, методът, който искаш да използваш трябва да проверява дали числото, което изследваш в момента се дели без остатък на всички прости числа преди него, като за целта трябва да записваш примерно в един List всички прости числа, които откриваш и за всяко следващо число да проверяваш дали се дели без остатък на всички числа от този списък.
Тук можеш да видиш решението ми от първата част на курса, в което използвам този подход:
http://pastebin.com/hM6MHE9c
*Тази част, която ти описвам е в checkIfPrime()
За конкретното домашно обаче се изисква да се използва друг подход, който можеш да разгледаш в линк-а към wikipedia по-горе.

от kdikov (3407 точки)



0
http://pastebin.com/u0dnzc4v
Някой ако може да каже защо това решение работи чудовищно бавно, ще съм благодарен. То е ясно защо де - върти много итерации, ама нещо не мога да му измисля оптимизация. До 5 млн - почти 18 мин...
Не считам нужно да печатам числата - само ги броя - това е достатъчно надеждна проверка - смята вярно, ако има търпение човек :)
edit: ето и обяснено решение с булев масив - благодаря на колегите за добрата идея :) http://pastebin.com/4NmkiEaW

от shristoff (747 точки)


0
Така е колега и при мен отнема над 10 мин. Просто програмата извършва много операции. До колкото си спомням, някой каза че съвременните процесори правели около 20 милиона пресмятания в секунда.

от stann1 (1378 точки)

0
едната причина е, че ми е бавна машината, но и решението не е велико явно :)

от shristoff (747 точки)



1
http://pastebin.com/4LSVAQgt Пиша този отговор само за да кажа: НЕ се опитвайте да решите задачата с LIST ... опитах и си блъсках главата сумата и време докато осъзная защо се получава такова огромно забавяне.

от Dzhambazov (570 точки)


1

Здравейте,

 

едно доста просто и изчистено решение от мен!

http://pastebin.com/91QwmF6G

Алгоритъма го прави за 0.1450174 секунди за всиски числа до 10 000 000.

По-бърз е от този на Теодор. :)

 

 

Чакам коментари!

 


от deyan.keray (266 точки)


0
Здравей, решението ти не намира само прости числа ! Смени 10М с 1000 и разгледай числата над 100 като 121,143,169,221..... - те не са прости.

от Dzhambazov (570 точки)

0
Простите числа не са само 2, 3 и 5. Числа като 7, 11, 13 и т.н. също са прости. Тъй като проверяваш едно число дали се дели само на 2, 3 и 5 допускаш числа като 77 = 11 * 7 за прости. Идеята на алгоритъма е да видиш дали текущото число се дели на някое от простите числа, които са по-малки от него и ако не се дели, тогава го обявяваш за просто.

от PBorukova (1129 точки)