Софтуерно Инженерство
Loading...
+ Нов въпрос
LubakaG avatar LubakaG 2 Точки

4.Sieve of Eratosthenes

http://pastebin.com/tfFVMiCK

Задачата минава нулевите тестове,проверих всичките "прости числа" и излизат както трябва,а в "Judge" системата ми дава 40 точки.Някой ако има съвет как да го оправя,ако може да пише :)

Тагове:
1
Programming Fundamentals
Silvave avatar Silvave 127 Точки
Best Answer

Здравей , въпреки че с този метод може да намериш всички прости числа, това реално не е "Sieve of Eratosthenes". С този метод взимаш всяко едно число от "1" до "n" и го проверяваш, дали се дели на "0" с число от "2" до "n" на квадрат, и ако се дели връща - false, а ако не се дели връща - true. 

Според условието на задачата трябва да придадеш на всяко число от "0" до "n" булева стойност - true, и като изглючиш "0" и "1" - false. След което взимаш първото просто число - "2" (дели се само на 1 и на себе си), запазваш/печаташ го като просто число и разделяш остналите числа до "n" с него. Ако резултата от делението им е "0", им прикачаш стойност false и после не минаваш  през тях да ги проверяваш, дали са прости, след като вече си им придал стойност false. След това взимаш следващото число, което е останало true, а това е "3", запазваш/печаташ го като просто число и разделяш остналите числа (които са все още със стойност true) до "n" с него и по същият начин, тези на които резултатът от делението им с него е "0" прикачаш - false. После прескачаш "4"(не го проверяваш), защото то е вече със стойност - false и минаваш към "5", защото е следващото със стойност - true. Запазваш/печаташ го и проверяваш кои от останалите числа до "n"се делят с него на "0" и им даваш - false. След това прескачаш "6" (false) и взимаш "7" (true), минаваш същата процедура и минаваш нататъка. Прескачаш "8,9,10" (false), взимаш "11" (true), минаваш пак същата процедура и продължаваш така до "n". Идеята е да не проверяваш числото, когато стигнеш до него, дали е просто, защото то вече не се е разделило на "0" с миналите прости числа преди него.

Ако не съм бил много ясен, ето и примерен код имплементиращ "Ситото на Ератостен" - http://pastebin.com/qwMHbMxS

4
Tangrila avatar Tangrila 21 Точки

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

http://pastebin.com/y7i1N6Ff

Някакви идеи?

0
04/06/2016 21:16:52
Silvave avatar Silvave 127 Точки

Не въртиш до края на посоченото число. Примерно с инпут от просто число - 7, 11,13, 17 и т.н., не ти изкарва последното просто число. Промени си булевата променлива на ред 15 (pastebin) и ще ти даде 100 точки.

3
Tangrila avatar Tangrila 21 Точки

Благодаря

1
slav.petkov avatar slav.petkov 26 Точки

Здравей, намерих ти грешката.

В Main метода, когато въртиш цикъла, трябва да е

for (int i = 1; i <= n; i++).

Поздрави!

2
aaaivaylo avatar aaaivaylo 16 Точки

Във for цикъла, в който проверяваш дали isPrime(i) == true, трябва да въртиш от 1 до n включително, защото ако например входа ти е 5, в случая ще ти покаже изход 2 и 3, а 5 също е просто число.

1
Plamen27 avatar Plamen27 598 Точки

За всички, които са изпитали трудност със задачата и решението, поствам решение,

което реализира точно алгоритъма на ситото на Ератостен cъгласно задачата:

http://pastebin.com/6ajRAg9x

4
YavorSpassov avatar YavorSpassov 133 Точки

Направил си го точно по псевдокода от Wikipedia. Забелязах, че i във втория ти цикъл може да започва от 1. Иначе, реших да посъкратя кода така :) :

 

        int n = int.Parse(Console.ReadLine());
        bool[] primes = new bool[n+1];
        for (int num = 0; num <= n; num++) primes[num] = true;
        primes[0] = primes[1] = false;

        for (int num = 1; num < primes.Length; num++) if (primes[num]== true)
        for (int multiplier = 2; multiplier*num<=n; multiplier++) primes[multiplier * num] = false;

        for (int num = 2; num <= n; num++) if (primes[num]==true) Console.Write(num+" ");

 

2
XuTkO avatar XuTkO 2 Точки

Тази задача разбереш ли й условието, няма проблеми. Ама докато го захапеш си ебало мамата.

0