I need a better algorithm for prime checking

Question 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;
}

Question 2

If you want to find every prime, then you can use a version of erathmus' sieve to generate the first 1000 or so, and then only check the list of prior primes, as they are the only meaningful factors by the fundamental theorem of algebra. If you want to find all the primes this is almost certainly faster than using a general number field sieve, which are designed to try to factor large numbers efficiently when you dont have a list of primes. Here is somthing that I wrote for Euler Project Number 7. It has two functions, one which uses erathmus' sieve to find all the primes up to 1000, then it uses the list of primes as an input to sequentially work of the next number which is prime via trial division of the list of primes.

public class NthPrime {

/**
 * @param args
 */
public static void main(String[] args) 
{
    int N = 10001;
    long startTime = System.currentTimeMillis();
    ArrayList<BigInteger> firstPrimes = primes(1000);
    System.out.println("The "+N +"th Prime is: " + Nthprime(firstPrimes, N));
    long stopTime = System.currentTimeMillis();
    long elapsedTime = stopTime - startTime;
    System.out.println(firstPrimes.toString());
    System.out.println(elapsedTime);

}

public static BigInteger Nthprime(ArrayList<BigInteger> primes, int N)
{
    if(N < primes.size())
    {

        return primes.get(N-1);

    }



    BigInteger start = primes.get(primes.size()-1);
    boolean bool = true;
    BigInteger ZERO = new BigInteger("0");
    BigInteger ONE = new BigInteger("1");
    BigInteger j = new BigInteger("1");
    while(bool)
    {
        boolean hasfactor = false;
        for(int i=0; i<primes.size(); i++)
        {

            BigInteger Q = start.add(j);
            BigInteger remainder = Q.mod(primes.get(i));

            if(remainder.equals(ZERO))
            {
                hasfactor = true;
                break;
            }
        }

        if(!hasfactor)
        {
            primes.add(start.add(j));

        }

        if(primes.size() == N)
        {
            bool = false;
        }

        j = j.add(ONE);
    }

    return primes.get(primes.size()-1);

}


public static ArrayList<BigInteger> primes(int N)
{
    boolean[] primes = new boolean[N+1];


    for(int j = 0; j<N+1; j++)
    {
        primes[j] = true;
    }
    int i = 2;
    while(i < N+1)
    {
     if(primes[i])
        {
            int j = 2*i;
            while(j<N+1)
            {
                primes[j] = false;
                j = j+i;

            }
        }
     i++;
    }
    ArrayList<BigInteger> allprimes = new ArrayList<BigInteger>();
    for(i=2; i<N+1; i++)
    {
        if(primes[i])
        {
            allprimes.add(new BigInteger((new Integer(i)).toString()));
        }
    }

    return allprimes;


}

}