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();
}

No comments:
Post a Comment