Хочу предложить вашему вниманию аналитическую задачу

[Dipost]

Доброго времени суток. Меня очень заинтересовала одна задачка. Собственно, вот она: "Дано натуральное число N. N=a*b. а и b-простые числа (делятся только на единицу и на самого себя). Аналитически найти а и b." Должен же быть какой голову ломал - вообще никаких идей нет, но кажется, что в таблице простых чисел есть какая то закономерность. Читайте, думайте, делитесь мыслями))

[SkuLLL]

Возможно a и b=1, это так от балды в голову пришло))

[Ezhuk]

SkuLLL, с каких пор 1 это простое число?

Dipost, надо программу написать или что-то другое?


Если программу то вот набросал, вроде работает =)

#include "stdio.h"
int main(){
	int n;
	scanf("%d", &n);
	for(int i=2;i<=n/2;i++){
		int temp=2,count=0;
		while(temp<=i/2){
			if(i%temp==0)
				count=1;
			temp++;
		}
		temp=2;
		if(n%i==0){
			int k=n/i;
			if(count==0)
				while(temp<=k/2){
					if(k%temp==0)
						count=1;
					temp++;
				}
			if(count==0){
				printf("%d = %d * %d\n",n,i,k);
				
				return 0;
				}
		}
	}
	puts("Impossible");
	return 0;
}

[p51x]

"Дано натуральное число N. N=a*b. а и b-простые числа (делятся только на единицу и на самого себя). Аналитически найти а и b." Должен же быть какой голову ломал - вообще никаких идей нет,

Долго смеялся! БОльшая часть криптографии основана на сложности факторизации.

но кажется, что в таблице простых чисел есть какая то закономерность.

Как найдете ее,то прямой путь в институт Клея за лямом.

П.С. Пока только перебор, вероятностные тесты и некоторые частные случаи.