I need a better algorithm for prime checking

Question

Primes are really strange... I created this simple pattern out of boredom. I haven't seen any of similarity online. As you see, the picture has lines of absence depending on the scale you choose, this is ranging from values 1 to 1000000

I intend on going from values 1 - 25,000,000 and perhaps 1 - 10,000,000,000

Perhaps the use of sieve techniques would help, but I need an adequate java implementation, I use the classic prime checker consisting of 2 for-loops which really chows time.

EDIT: here is a sample of my code

 boolean checkPrime(long a)
 {
 long count = 0L;
    for(long op = 1;op<=a;op++)  
            if(a%op==0)
                     count++;

  return count ==2;
 }

Update: I found a simple optimisation measure for my code

 boolean checkPrime(long a)
 {
 long count = 0L;
    for(long op = 1;op<=a;op++)  
            if(a%op==0)
                      {
                       count++;
                               if(count>2)break; //here it is
                      }

  return count ==2;
 }

Code seems to run x10 faster

I finally chose to create this and stick with it.

package superprime;
public class SuperPrime {
    static java.util.List primes = new java.util.ArrayList<Long>();
    public static void main(String[] args) {
        Thread.currentThread().setPriority(Thread.MAX_PRIORITY);
        long start = System.currentTimeMillis();
       primes.add(2);
       boolean flag = true;
       long u =primes.size();long wow;double val;
    for(long e = 3L; e<10000000;e=e+2){
        flag = true;
        for( wow = 0;(wow< u)&&flag;wow++){
            if(e%(Long.parseLong(primes.get((int)wow)+""))==0)
           flag=false;

        }
        if(flag)primes.add(e);
        val = Double.parseDouble(primes.get((int)u)+"");
        if((val == Math.sqrt(e+1))||(val == Math.sqrt(e+2)))u++;
   // if(e%250000==0)System.out.println((System.currentTimeMillis()-start)/1000.0+" @ "+e);
    }long end =System.currentTimeMillis();
     System.out.println(""+(end-start)/1000.0);
     wow = 1;
for(Object h : primes)System.out.println(++wow+"\t"+(Long.parseLong((h)+"")));

    }

}

Answer 1

Code you presented is makeing a operations for every a. It is simple way to improve it:

boolean checkPrime(long a)
 {
 long count = 0L;
 for(long op = 2;op*op<=a;op++)  
        if(a%op==0)
                 return false;

  return true;
 }

Now it makes only sqrt(a) operations and always gives right answer. For beter execution times are randomised algorithms like Rabin-Milers algorithm: http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

I include mine implementation in c++ of Rabin-Milers algorithm.

#include<iostream>
#include<cmath>
#include<cstdlib>
using namespace std;

const int losowania=20;

long long pote(long long x,long long k,long long m)//this function is counting (x^k)mod m
{
if(k==1)
{
    return x%m;
}
if(k%2==0)
{
    long long a=pote(x,k/2,m);
    return ((__int128_t)((__int128_t)a*(__int128_t)a)%(__int128_t)m);
}
else
{
    long long a=pote(x,k-1,m);
    return ((__int128_t)((__int128_t)a*(__int128_t)x)%(__int128_t)m);
}
}

bool Rabin_Miler(long long p,long long x)
{

if(pote(x,p-1,p)!=1)
{
    return false;
}
long long wyk=(p-1);
while(wyk%2==0)
{
    wyk/=2;
}
long long teraz=pote(x,wyk,p);
if(teraz==1)
{
    return true;
}
while(teraz!=1&&teraz!=p-1)
{
    teraz=(__int128_t)((__int128_t) teraz*(__int128_t)teraz)%(__int128_t)p;
}
if(teraz==1)
{
    return false;
}
else
{
    return true;
}
}

bool is_prime(long long p)
{
srand(100);
    for(int i=0;i<losowania;i++)
    {
        if(!Rabin_Miler(p,(rand()%(p-1))+1))
        {
            return false;
            break;
        }
    }
return true;
}