Простые шестизначные числа

[Serge_Bliznykov]

полностью согласен с s-andriano!

(programmerhpkk, посмотрите на форуме, уже были данные примеры эффективной проверки числа на простоту)

добавлю, что если заданное число K кратно 3-м, то можно сразу выводить ответ, что простых чисел с такой суммой цифр НЕТ (см. признаки делимости).


update
А почему все решили, что автору топика нужно решение на С ? Я, например, могу на Паскале решение выложить

[KooKish]

О боже.... я задание не так понял. В голове не простые числа держал а целые...
Сейчас похимичим...

А почему все решили, что автору топика нужно решение на С ?

Форум экстрасенсов же...

[KooKish]

Ну быстрей чем у programmerhpkk, но тоже подождать приходится В принципе если еще посидеть и постараться, то можно время сократить. Но это уже забота автора

#include <iostream>
#include <conio.h>

using namespace std;

int main(){
	setlocale(LC_ALL, "rus");
	int n, a, b, y, count;
	double x, z;
	cout << "Введите число от 1 до 54: ";
	cin >> n;
	for(int i=100000;i<1000000;i++){
		b = 0;
		a = i;
		for(int tmp=0;tmp<6;tmp++){
			b += a%10;
			a = a/10;
		}
		if( b == n ){
			x = i;
			count = 0;
			for(int j=2;j<x;j++){
				z = x / j;
				y = x / j;
				if( z / y == 1 )
					break;
				if( j == x - 1 )
					cout << x << "  ";
			}
		}
	}
	getch();
}

[Serge_Bliznykov]

			for(int j=2;j<x;j++){
				z = x / j;
				y = x / j;
				if( z / y == 1 )
					break;
				if( j == x - 1 )
					cout << x << "  ";

Это что за кошмарный ужас?! я потрясён...



если не использовать решето Эратосфена для поиска простых чисел,
тогда я бы обратил Ваше внимание на функцию PrimeNumber из этого поста
или функцию isPrime из этого
да. и вместо корня квадратного из числа n можно использовать цикл вида: for (int i=2;i*i<=n;i++)

[KooKish]

Это что за кошмарный ужас?! я потрясён...

Это фирменная проверка на ПРОСТОЕ число )))))) сам придумал :D да я от балды делал. говорю же надо немного переделать Кстати тормозит из за этой части.

[Serge_Bliznykov]

Это фирменная проверка на ПРОСТОЕ чис

извините меня за прямоту, но это не проверка, это "фирменный" БРЕД!

[KooKish]

Работает же :D Мне всегда говорили что я делаю не как все а через ж. Но в итоге все работает. Помню как делфи сдавал, так мне препод говорит: "Она у тебя даже запускаться не должна, а в итоге работает". Это конечно не есть хорошо. Но все же.

[Serge_Bliznykov]

Работает же :D

угу. кое-как, но работает.
Но!
во-первых, не поленитесь, посмотрите решения по ссылкам, которые я привёл.

во-вторых, откройте для себя операцию целочисленного деления %
ваше z = x / j; y = x / j; if( z / y == 1 ) break;
заменяет строчка кода if (x%j == 0) break

в-третьих, не нужно перебирать все числа до x достаточно беребирать до корня квадратного из x - поверьте мне, цикл от 2 до 1000 выполнится НАМНОГО быстрее, чем цикл от 2 до 1000000!

[alexander13]

Сообщение от Serge_Bliznykov

цикл от 2 до 1000 выполнится НАМНОГО быстрее, чем цикл от 2 до 1000000!

Не читал всю тему, но если там используется метод перебора, то лучше сначала проверять на четность, тогда кол-во чисел для перебора еще сократится вдвое =)
Ну, цикл там будет тогда что-то типа for (i = 3; i*i <= n; i+=2)

[Serge_Bliznykov]

Сообщение от alexander13

Не читал всю тему, но если там используется метод перебора, то лучше сначала проверять на четность, тогда кол-во чисел для перебора еще сократится вдвое =)

alexander13, полностью согласен! (пруф в любом моём сообщении, где я привожу свой любимый код проверки числа на простоту на Паскале... )