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

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

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.

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

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

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

Громоздкий?

man Sieve of Eratosthenes

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

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

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

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

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

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

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

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

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

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

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

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

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

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; }

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

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; }

int main()
{
	int i, j;

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

так;)

s/if(j > sqrt(i))/if(j > j1)/

Я бы предложил посчитать все простые числа вот так =))))))

perl -wle '(1 x $_) !~ /^(11+)\1+$/ && print while ++ $_'

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 уже сильно зависит от того, что вам от простых чисел надо.

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

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