// IntegerPrimality (2013) import java.io.*; public class IntegerPrimality { // Variables private static final String FILE_NAME="primes.data"; private static final int LIMIT=Integer.MAX_VALUE; // Inclusive private static final int ARRAY_LENGTH=(LIMIT/32)+1; // +1 because inclusive, so even 0 requires array length to be 1 private static final int[] BITS={(1<<0) ,(1<<1) ,(1<<2) ,(1<<3) ,(1<<4) ,(1<<5) ,(1<<6) ,(1<<7) , (1<<8) ,(1<<9) ,(1<<10),(1<<11),(1<<12),(1<<13),(1<<14),(1<<15), (1<<16),(1<<17),(1<<18),(1<<19),(1<<20),(1<<21),(1<<22),(1<<23), (1<<24),(1<<25),(1<<26),(1<<27),(1<<28),(1<<29),(1<<30),(1<<31)}; private static final int[] primesarray=new int[ARRAY_LENGTH]; private static boolean ready=false; // Accessors // This may take hours but need to be done just once public static void generate() { System.out.println("IntegerPrimality.generate(): Creating file \""+FILE_NAME+"\" for numbers [0.."+LIMIT+"]"); for (int n=0; n=0; n++) { if (n%1000000==0) { System.out.println("IntegerPrimality.generate(): ..."+n+"/"+LIMIT); } if (generateTestPrime(n)) { primesarray[n/32]|=(1<<(n%32)); } } try { File file=new File(FILE_NAME); DataOutputStream output=new DataOutputStream(new FileOutputStream(file)); for (int n=0; ntime) { System.out.println("IntegerPrimality.init(): ..."+((int)((100.0*n/ARRAY_LENGTH+0.5)))+"%"); time+=10000L; } } input.close(); ready=true; System.out.println("IntegerPrimality.init(): Ready"); } catch (Exception e) { e.printStackTrace(); } } // For max speed, no boundary checks or checking if array is ready // Make sure init() is called before using this, otherwise this always returns false public static boolean isPrime(int n) { // return ((primesarray[n/32]&(1<<(n%32)))!=0); // 13745ms // return ((primesarray[n/32]&(1<<(n&31)))!=0); // 7587ms // return ((primesarray[n>>5]&(1<<(n&31)))!=0); // 3330ms // return ((primesarray[n>>5]&BITS[n&31])!=0); // 2885ms return ((primesarray[n>>5]&BITS[n&31])!=0); } // Private private static boolean generateTestPrime(int x) { // Small primes if (x==2 || x==3 || x==5 || x==7 || x==11 || x==13 || x==17) { return true; } // Small composites if (x<19) { return false; } // Test dividing with 2 and 3 if (x%2==0) { return false; } if (x%3==0) { return false; } // Test dividing with 5,7,11,13,17,19,23... int max=(int)(Math.sqrt(x)+1), add=2; for (long div=5; div<=max; div+=add, add=6-add) { if (x%div==0) { return false; } } // Prime return true; } }