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

[makskovalko]

Здравствуйте! Напишите, пожалуйста, программу, которая бы выводила все простые шестизначные числа с суммой цифр, равной К.

[KooKish]

Самый простой, НО не очень корректный вариант.

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

using namespace std;

int main(){
	setlocale(LC_ALL, "rus");
	int n, a, b, c, d, e, f;
	cout << "Введите число от 6 до 54: ";
	cin >> n;
	for(a=1;a<10;a++)
		for(b=1;b<10;b++)
			for(c=1;c<10;c++)
				for(d=1;d<10;d++)
					for(e=1;e<10;e++)
						for(f=1;f<10;f++)
							if( a + b + c + d + e + f == n )
					                cout << a << b << c << d << e << f << "  ";
	getch();
}

[was3110]

О простых числах представление своеобразное...

[s-andriano]

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

О простых числах представление своеобразное...

О шестизначных - тоже.
100000, 110000, 200000 - разве не шестизначные?

[KooKish]

Я нули не учитывал, т.к. отсчитывал от всех 1 до всех 9, принципе исправляется довольно просто.
хм, хотя верно, в моем случае, нулей вообще не будет. Благодарю за внимательность.

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

using namespace std;

int main(){
	setlocale(LC_ALL, "rus");
	int n, a, b, c, d, e, f;
	cout << "Введите число от 0 до 54: ";
	cin >> n;
	for(a=0;a<10;a++)
		for(b=0;b<10;b++)
			for(c=0;c<10;c++)
				for(d=0;d<10;d++)
					for(e=0;e<10;e++)
						for(f=0;f<10;f++)
							if( a + b + c + d + e + f == n )
					                cout << a << b << c << d << e << f << "  ";
	getch();
}

[programmerhpkk]

Собственно вот. Вроде все правильно выдает, только вычисляет долго:

#include <iostream>
#include <conio.h>
using namespace std;
int main()
{int s=0;
int n,z;
cout<<"Vvedite naturalnoe chislo menshe 55\n";
cin>>n;
	for(int i=100000 ; i<1000000;i++)
	{	
		s=0;
		for(int j=2;j<i;j++)		
			if(!(i%j)) s++;
	
			if (!s) 
			{	
				z=i;
				while(z)
					{
						s=s+(z%10);
						z=z/10;
					}
				if (s==n) cout<<i<<" ";
			}
	}
getch();
}

[programmerhpkk]

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

Я нули не учитывал, т.к. отсчитывал от всех 1 до всех 9, принципе исправляется довольно просто.
хм, хотя верно, в моем случае, нулей вообще не будет. Благодарю за внимательность.

Чёт совсем не то выводит...

[makskovalko]

Программа должна выводить все ПРОСТЫЕ шестизначные числа.

[programmerhpkk]

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

Программа должна выводить все ПРОСТЫЕ шестизначные числа.

Ну моя и выводит все ПРОСТЫЕ шестизначные числа с суммой цифр, равной К.
Вот в процесе вывода, просто ждать пока весь цикл пройдет лень было.

[s-andriano]

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

Ну моя и выводит все ПРОСТЫЕ шестизначные числа с суммой цифр, равной К.
Вот в процесе вывода, просто ждать пока весь цикл пройдет лень было.

Ну да.
"Лесенка" в коде немножко странно выполнена поэтому трудно с первого взгляда понять, что именно делается.

только вычисляет долго:

Ну так написано на редкость неоптимально.
Если пытаться подправить существующий код, то следует:
1. Проверку на простоту достаточно проводить по максимуму до sqrt(i), а не до i.
2. Цикл проверки на простоту можно прерывать, когда найден первый делитель, не обязательно искать все.
3. Целесообразно сначала подсчитывать сумму цифр (как менее ресурсоемкую операцию) и только потом - по условию - проверку на простоту (как более ресурсоемкую).
4. Перебор достаточно осуществлять только по нечетным числам, проверку на делимость начиная с 3.

Ну а по-хорошему, нужно менять алгоритм, тогда 99% времени будет тратиться только на вывод на экран:
1. Составить таблицу простых чисел в диапазоне 1000000-999999 (решето Эратосфена).
2. Просмотреть таблицу, для простых подсчитать сумму цифр, при нужной сумме - вывод на печать.
Минус такого алгоритма - необходимо несколько десятков Кбайт памяти (в простейшем случае 55К).