VB icon

Matrix Sieve- new algorithm for finding primes

Email
Submitted on: 8/1/2015 9:53:24 AM
By: Boris Sklyar  
Level: Advanced
User Rating: Unrated
Compatibility: C++ (general)
Views: 2045
 
     Calculates prime numbers in sequences S1=6p+5 and S2=6p+7, p=0,1,2,3,...up to N=2*10^19 in the range up to N2-N1=10^6 on the base of derived "matrix definition" of primes.

 
code:
Can't Copy and Paste this?
Click here for a copy-and-paste friendly version of this code!
				
//**************************************
// Name: Matrix Sieve-new algorithm for finding primes
// Description:Calculates prime numbers in sequences S1=6p+5 and S2=6p+7, p=0,1,2,3,...up to N=2*10^19 in the range up to N2-N1=10^6on the base of derived "matrix definition" of primes.
// By: Boris Sklyar
//**************************************

#include <cstdlib>
#include <iostream>
#include <math.h>
#include <ctime>
using namespace std;
 main( ) 
{
 /* 1S MATRIX SIEVE*/
/*FINDING PRIMES IN THE RANGE (N1;N2) in sequence S1=6*P*+5*/ 
 /*Authors: B.Sklyar, D.Sklyar, I.Sklyar*/
 /* N1>7; N2<2 000 000 000 000 000 000; N2-N1< 1 000 000*/ 
 unsigned long long int N1=111222333444555000; unsigned long long int N2 =111222333444555900;
unsigned long long int pr1=floor(N1/6); unsigned long long int pr2=ceil( N2/6);
int q=170000; int R2[q] ; int qm=pr2-pr1; unsigned long long int S1[q] ; int q2, q1;
 for (q=1;q<qm;q++) 
 R2[q] =1;
unsigned long long int i, j, P1, P2,B, K;
unsigned long long int i2= sqrt( pr2/6)+1;
 long long int j1, j2;	
 int L1=0;
for ( i=1;i<i2;i++)
{ B=6*i*i-1; K=5+6*( i-1);
j2=(pr2+K-B)/K+2;j1=j2-qm/K-2;
if (j1<1) j1=1;
 for(j=j1; j<j2;j++)
{ P1=B+K*( j-1);
if(( P1>pr1)&&( P1<pr2)) 
 { q1=P1-pr1; R2[ q1] =0;
 } }
 B=6*i*i-1; K=K+2;
 j2=(pr2+K-B)/K+2;j1=j2-qm/K-2;
if (j1<1) j1=1;
for(j=j1; j<j2;j++)
{ P2=B+K*( j-1);
	 if(( P2>pr1)&&( P2<pr2))
 {q2=P2-pr1; R2[ q2] =0;
 } } }
 cout<<"\ni2="<<i2<<";pr2="<<pr2<<" \n";
for ( q=1;q<qm;q++) { S1[q] =R2[q]*((pr1+q)*6+5);if (S1[q]%5==0) continue;L1=L1+1;
 cout<<"q="<<q<<"; Prime in S1[P]=6*P+5="<<S1[ q]<<" \n";} 
cout<<"\nP=pr1+q; pr1="<<pr1<<" \n";
cout<<"number of Primes in the range (N1;N2) in S1 L1="<<L1<<" \n";
 cout<<" run time (ms)=";
cout<<clock();
 system("PAUSE");
 return EXIT_SUCCESS;
 
}
#include <cstdlib>
#include <iostream>
#include <math.h>
#include <ctime>
using namespace std;
 main( ) 
{
 /* 2S MATRIX SIEVE*/
/*FINDING PRIMES IN THE RANGE (N1;N2) in sequence S2=6*P*+7*/ 
 /*Authors: B.Sklyar, D.Sklyar, I.Sklyar*/
 
 /* N1>7; N2<2 000 000 000 000 000 000; N2-N1< 1 000 000*/ 
 
unsigned long long int N1=111222333444555000; unsigned long long int N2 =111222333444555900;
unsigned long long int pr1=floor(N1/6); unsigned long long int pr2=ceil( N2/6);
 
 int r=170000; int R2[r] ; int rm=pr2-pr1; unsigned long long int S2[r] ; int r2, r1;
 for (r=1;r<rm;r++) 
 R2[r] =1;
 unsigned long long int i, j, P1, P2,B, K;
unsigned long long int i2= sqrt( pr2/6)+1;
 long long int j1, j2;	
 int L2=0;
for ( i=1;i<i2;i++)
{ B=6*i*i-2*i-1; K=5+6*( i-1);j2=(pr2+K-B)/K+2;j1=j2-rm/K-2;
 if (j1<1) j1=1;
 for(j=j1; j<j2;j++)
{ P1=B+K*( j-1);
if(( P1>pr1)&&( P1<pr2)) 
 { r1=P1-pr1; R2[ r1] =0;
 } }
 B=6*i*i+2*i-1; K=K+2;
 j2=(pr2+K-B)/K+2;j1=j2-rm/K-2;
if (j1<1) j1=1;
for(j=j1; j<j2;j++)
{ P2=B+K*( j-1);
	 if(( P2>pr1)&&( P2<pr2))
 {r2=P2-pr1; R2[ r2] =0;
 } } }
 cout<<"\ni2="<<i2<<";pr2="<<pr2<<" \n";
for ( r=1;r<rm;r++) { S2[r] =R2[r]*((pr1+r)*6+7);if (S2[r]%5==0) continue;L2=L2+1;
 cout<<"r="<<r<<"; Prime in S2[P]=6*P+7="<<S2[ r]<<" \n";} 
cout<<"\nP=pr1+r; pr1="<<pr1<<" \n";
cout<<"number of Primes in the range (N1;N2) in S2 L2="<<L2<<" \n";
 cout<<" run time (ms)=";
cout<<clock();
 system("PAUSE");
 return EXIT_SUCCESS;
 
}


Other 2 submission(s) by this author

 


Report Bad Submission
Use this form to tell us if this entry should be deleted (i.e contains no code, is a virus, etc.).
This submission should be removed because:

Your Vote

What do you think of this code (in the Advanced category)?
(The code with your highest vote will win this month's coding contest!)
Excellent  Good  Average  Below Average  Poor (See voting log ...)
 

Other User Comments


 There are no comments on this submission.
 

Add Your Feedback
Your feedback will be posted below and an email sent to the author. Please remember that the author was kind enough to share this with you, so any criticisms must be stated politely, or they will be deleted. (For feedback not related to this particular code, please click here instead.)
 

To post feedback, first please login.