[Zadatak] Nalazenje prostih brojeva metodama koje su imale propuste (izostavljale pojedina resenja)
Dobio sam za seminarski da napisem neki programcic, pa mi treba pomoc.
Elem, zadatak glasi ovako:
U istoriji matematike predlagane su razne formule za generisanje
prostih brojeva. Ispostavilo se da su mnoge od njih bile pogresne, tj. pronadeni su slucajevi u
kojima ne generisu proste brojeve.
Napisati program u kojem bi se koristile bar tri takve formule i za svaku od njih pronalazio bar jedan
slucaj za koji formula ne daje prost broj.
Uputstvo. Jedna od takvih formula (ciji autor nije poznat) bila je
xn = n^2 + n + 41
Jos jedna formula, slicna prethodnoj, je:
xn = n^2 - 79n + 1601
U prvoj polovini 17. veka, Mersen je uveo pretpostavku da su brojevi oblika
2p - 1
prosti brojevi kad god je p prost broj. Ovakvi brojevi, u oznaci Mp, poznati su pod nazivom
Mersenovi brojevi. Mersenov broj M127 = 2^127 - 1, dugi niz godina drzao je rekord kao najveci
poznati prost broj. Na zalost, Mersenova pretpostavka nije bila tacna. Postoji veci broj Mersenovih
brojeva koji nisu prosti. Dakle, i Mersenovu formulu mozemo svrstati u prethodnu grupu.
Evo kako sam ja poceo:
#include<stdio.h>
#include<math.h>
int prost(int n);
int main(){
int i=1,k=1;
int n;
n=i*i+i+41;
while (prost(n)==1)
{
n=i*i+i+41;
i++;
}
printf("Prvi prost broj za koji ne vazi formula n^2 + n + 41 je: %d\n",n);
getchar();
getchar();
}
int prost(int n)
{
float k;
int i;
if ((n%2==0 && n!=2) || n==1)
return 0;
k=sqrt(n);
for(i=3; i<=k; i+=2)
if (n % i == 0)
return 0;
return 1;
}
E sad, znam da ovo nije najsrecnije resenje.. zapravo, cudim se sto uopste radi.
Za drugu formulu isto to ne radi, tj. dobijam 1523 koji je prost, a trecu nisam ni probao..
Ako moze neka pomoc.. Hvala.
 |  |
 |
