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 599 Точки

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

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

http://pastebin.com/6ajRAg9x

4
YavorSpassov+deleted! avatar YavorSpassov+deleted! 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
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.