Sunday, October 5, 2008

Prime numbers - new criteria

If we want to determine all the prime numbers smaller than n we have to check the divisors till sqrt{N-p}; here p is the first divisor of the greather number smaller than n.
In this case, for n=10000000(10mil), we make with 7901 steps lesser than the classic method - to go till sqrt{N}.

The classic criteria:

//21086848011 - the total number of steps
#include
#include
#include

unsigned long int i, n, p;
unsigned long int V;
long double S=0;

FILE * f;

void main(void)
{
//printf("Intr n:");
//scanf("%d",&n);

f=fopen("orig.txt","w+");

for(n=2;n<10000000;n++)
{
p=1;
V=(int)ceil(pow(n,0.5));
//printf("\nV=%d\n",V);
for(i=2;i<=V+1;i++)
{
if((n%i)==0) p=0;
S++;
}
if(p==0)
;//printf("NOK");
else
fprintf(f,"%Ld\n",n);
}
printf("\nAm terminat...");
fprintf(f,"S=%.1Lf",S);
fclose(f);
getch();

}

The new criteria:

//21086840110 - the total number of steps
//Diff==7901
#include
#include
#include

unsigned long int i, n, p;
unsigned long int V, X, G;
long double S=0;

FILE * f;

void main(void)
{
//printf("Intr n:");
//scanf("%d",&n);

f=fopen("prime.txt","w+");

for(n=2;n<10000000;n++)
{
p=1;
G=0;
X=0;
V=(int)ceil(pow(((float)n-X),0.5));
//printf("\nV=%d\n",V);
for(i=2;i<=V+1;i++)
{
if((n%i)==0) p=0;
else if(G==0)
{
X=i;
G=1;
V=(int)ceil(pow(((float)n-X),0.5));
}
S++;
}

if(p==0)
;//printf("NOK");
else
fprintf(f,"%Ld\n",n);
}
printf("\nAm terminat...");
fprintf(f,"S=%Lf",S);
fclose(f);
getch();

}