More Efficient Prime Searching Algorithm?

[Draco]

I started working on some Project Euler problems today, and I'm having problems with the one that seeks the sum of all prime number less than 2000000.
It's running very slowly, so I was wondering if there existed a faster prime searching algorithm than the one I have now. (It's currently some sort of inefficient prime sieve.)
Here is the code:

public class Problem10 {
	
	public static void main(String args[]){
		
		int sum = 0; 
		
		boolean[] a = primesList();
		
		for(int i = 0; i<1999999; i++){
			
			if(!a[i]) sum+=i+2;
			
		}
		
		System.out.println(sum);
		
	}

	
	public static boolean[] primesList(){
		
		boolean[] a = new boolean[1999999];
		for(int i = 0; i<1999999; i++){
			
			if(!a[i]){

				int j = i+2;
				for(int k = i+3; k<2000001; k++){
					
					if(divTest(k, j)) a[k-2]=true;
					
				}
					
				
			}
			if(i%10000==0) System.out.println(i);
		}
		
		return a; 
		
	}
	
	public static boolean divTest(int i, int j){
		
		boolean b = false; 
		if (i/j==((double) i)/j) b=true; 
		return b;
		
	}
	
}

[JosAH]

For a sieve you don't need to divide anything; for all multiples of 2 (except 2 itself) clear the corresponding flag. Check the first next number with its flag set, say x; clear all multiples of x (except x itself) and repeat the process until done. While checking for those numbers with their flag set in the outer iteration, you might as well add them to a total value; that way, when you're done with your sieve you're done with your entire algorithm.

kind regards,

Jos

[Ksharp]

Yes. there are some more efficient way.
Did you search it at Wiki . PRIME NUMBER

for (int i=1;i < sqrt(2000000);i++ )
for (int j=1;j <=2000000;j++)
if a[j]= multiplies of i then call missing a[j]


Ksharp

[JosAH]

That isn't very efficient; better try an ordinary sieve:

		boolean[] b= new boolean[100000];
		
		b[0]= b[1]= true;
		
		for (int x= 2; x < b.length; x++)
			if (!b[x])
				for (int y= x+x; y < b.length; y+= x)
					b[y]= true;

if b[x] is true x is not a prime number.

kind regards,

Jos

[Singing Boyo]

boolean[] b= new boolean[100000];
		
b[0]= b[1]= true;
		
for (int x= 2; x < b.length; x++)
	if (!b[x])
		for (int y= x+x; y < b.length; y+= x)
			b[y]= true;

Wouldn't it be more efficient to only check for values of x up to b.length/2? It seems a bit ridiculous to be incrementing x when x+x will always be greater than or equal to b.length, so the inner for loop will never execute once x > b.length/2.

So instead of what josAH posted, unless I'm missing something, this would end faster, if not by much for tests up to less than a million or so:

boolean[] b= new boolean[100000];
		
b[0]= b[1]= true;
for (int x= 2; x < b.length/2; x++)
	if (!b[x])
		for (int y= x+x; y < b.length; y+= x)
			b[y]= true;

[JosAH]

Wouldn't it be more efficient to only check for values of x up to b.length/2? It seems a bit ridiculous to be incrementing x when x+x will always be greater than or equal to b.length, so the inner for loop will never execute once x > b.length/2.

So instead of what josAH posted, unless I'm missing something, this would end faster, if not by much for tests up to less than a million or so:

boolean[] b= new boolean[100000];
		
b[0]= b[1]= true;
for (int x= 2; x < b.length/2; x++)
	if (!b[x])
		for (int y= x+x; y < b.length; y+= x)
			b[y]= true;

It is, indeed, a bit more efficient, i.e. for the last half (here 500,000) nothing needs to be done and the inner loop doesn't execute; but for the first half many more iterations have been made; 1e6/2+1e6/3+1e6/4 ...

kind regards,

Jos