LINUX.ORG.RU

Простые числа - не понимаю


0

0

Есть программа, которая вычисляет простые числа от 2 до 100.
Никак не понять.
Кто понимает, расскажите на примере, когда добираемся до 17 числа.

#include <iostream>
using namespace std;

int main()
{
	int i, j;

	for(i=2; i<100; i++) {
		for (j=2; j <= (i/j); j++)
			if(!(i%j)) break;
		if(j > (i/j)) cout << i << " - prostoe\n";
	}
	return 0;
}
anonymous

Re: Простые числа - не понимаю

Переписываю, чтоб понятно было:

int main()
{
	int i, j;

	for(i = 2; i < 100; i++) {
		for (j = 2; j <= sqrt(i); j++)
			if(i % j == 0) break;
		if(j > sqrt(i))
			cout << i << " - prostoe\n";
	}
	return 0;
}

Внешний цикл - по проверяемым числам. Внутренний - по возможным делителям.
Если во внутреннем цикле делители не были найдены, то j будет больше
квадратного корня из i.

naryl ★★★★★ ()

Re: Простые числа - не понимаю

Простое число - делится нацело только на себя и на 1. Первый цикл пробегает по ряду от 2 до 100, второй цикл от 2 до половины исследуемого числа (если делитель болше половины то очевидно делиться нацело чило не будет тк результат будет меньше 2), в цикле послеовательно делится исследуемое число и проверяется остаток от деления - если он равен нолю - значит исследуемое число делится нацело и цикл прерывается. Далее исследуется - если делитель болше половины исследуемого числа (условие нормального выхода из цикла) то число простое и оно выводится на устройство вывода если нет (выход по break) число не простое. Блин как в первом классе :)

anonymous ()

Re: Простые числа - не понимаю

Спасибо. въехал

anonymous ()

Re: Простые числа - не понимаю

Вообще-то это плохой способ генерации и/или проверки простых чисел.

anonymous ()
Ответ на: Re: Простые числа - не понимаю от imp

Re: Простые числа - не понимаю

решето Эратосфена тяжеловато на больших диапазонах (~10^10)

а указанный алгоритм плох, что он лишний раз проверят четные числа: пусть даже только на делимость на 2, но это уже внушительная трата процессорного времени.

anonymous ()
Ответ на: Re: Простые числа - не понимаю от anonymous

Re: Простые числа - не понимаю

>второй цикл от 2 до половины исследуемого числа

до sqrt(исследуемого числа):

j<=i/j <==> j*j<=i <==> j<=sqrt(i)

последний вариант предпочтительней, т.к. корень будет вычислен только один раз (если включена соотв. оптимизация), тогда как деление будет вычисляться каждый проход цикла.

anonymous ()
Ответ на: Re: Простые числа - не понимаю от anonymous

Re: Простые числа - не понимаю

> Так чётные тоже бывают простыми - пример число 2.

это понятно. но я и не говорил, что его надо исключать!

anonymous ()
Ответ на: Re: Простые числа - не понимаю от anonymous

Re: Простые числа - не понимаю

>второй цикл от 2 до половины исследуемого числа

хм кстати нет, не до половины, а до квадратного корня: j=i/j => i=j*j

Поняли, почему именно до корня считать нужно, а почему дальше - не рационально?

anonymous ()
Ответ на: Re: Простые числа - не понимаю от anonymous

Re: Простые числа - не понимаю

Переписываю, чтоб правильно было...

int main() { int i, j;

for(i = 2; i < 100; i++) { double j1 = sqrt(i); // так правильно for (j = 2; j <= j1 ; j++) if(i % j == 0) break; if(j > sqrt(i)) cout << i << " - prostoe\n"; } return 0; }

anonymous ()
Ответ на: Re: Простые числа - не понимаю от anonymous

Re: Простые числа - не понимаю

Переписываю, чтоб правильно было...

int main() { int i, j;

for(i = 2; i < 100; i++) { double j1 = sqrt(i); // так правильно for (j = 2; j <= j1 ; j++) if(i % j == 0) break; if(j > sqrt(i)) cout << i << " - prostoe\n"; } return 0; }

anonymous ()
Ответ на: Re: Простые числа - не понимаю от anonymous

Re: Простые числа - не понимаю

printf("2\n");
for (int i = 3; ; i+=2) {
if (простое(i)) printf("%d\n", i);
}

А ещё можно так:
printf("2\n");
printf("3\n");
printf("5\n");
for (int i = 1;; i++) {
test_and_print(6*i+1);
test_and_print(6*i+5);
}

void test_and_print(int i) {
if (простое(i)) printf("%d\n", i);
}

И так далее.

Дальнейшее развитие идеи afaik уже сильно зависит от того, что вам от простых чисел надо.

alexsaa ()

Re: Простые числа - не понимаю

>Простые числа - не понимаю

s/Простые/Сложные/

xTERM ★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.