4.Sieve of Eratosthenes
http://pastebin.com/tfFVMiCK
Задачата минава нулевите тестове,проверих всичките "прости числа" и излизат както трябва,а в "Judge" системата ми дава 40 точки.Някой ако има съвет как да го оправя,ако може да пише :)
Във форума е въведено ограничение, което позволява на потребителите единствено да разглеждат публикуваните въпроси.
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
Здравей, намерих ти грешката.
В Main метода, когато въртиш цикъла, трябва да е
for (int i = 1; i <= n; i++).
Поздрави!
Във for цикъла, в който проверяваш дали isPrime(i) == true, трябва да въртиш от 1 до n включително, защото ако например входа ти е 5, в случая ще ти покаже изход 2 и 3, а 5 също е просто число.
За всички, които са изпитали трудност със задачата и решението, поствам решение,
което реализира точно алгоритъма на ситото на Ератостен cъгласно задачата:
Направил си го точно по псевдокода от 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+" ");
Тази задача разбереш ли й условието, няма проблеми. Ама докато го захапеш си ебало мамата.
И аз имам затруднения с judge-a, и аз получавам 40, а програмата ми работи отлично доколкото успях да проверя.
http://pastebin.com/y7i1N6Ff
Някакви идеи?
Не въртиш до края на посоченото число. Примерно с инпут от просто число - 7, 11,13, 17 и т.н., не ти изкарва последното просто число. Промени си булевата променлива на ред 15 (pastebin) и ще ти даде 100 точки.
Благодаря