Java – improved main screen algorithm

I'm trying to make a good java program to generate prime numbers from 1 to n (mainly for project Euler problems)

At present, my algorithm is as follows:

Initializes a Boolean array (bitarray if n is large enough), so they are false and store a set of integers for storing prime numbers

Set an integer where s is equal to the lowest prime number, (i.e. 2)

S is < = sqrt (n) set all multiples of S (starting from S ^ 2) to true in the array / bit array Find the next smallest index in array / bitarray, which is false, and use it as the new value of S ENDWHILE. Traverse the array / bit array, and put the corresponding index in the primes array for each false value Now, I try to skip numbers that are not in the form of 6K 1 or 6K 5, but this only makes me speed up ~ 2 times, and I see that the program runs faster than me (although the code is very complex), such as a here

What can I do to improve?

Editor: OK, this is my actual code (for 1E7 n):

int l = 10000000,n = 2,sqrt = (int) Math.sqrt(l);
boolean[] nums = new boolean[l + 1];
int[] primes = new int[664579];

while(n <= sqrt){
    for(int i = 2 * n; i <= l; nums[i] = true,i += n);
    for(n++; nums[n]; n++);
}

for(int i = 2,k = 0; i < nums.length; i++) if(!nums[i]) primes[k++] = i;

It runs about 350ms on my 2.0GHz machine

Solution

S is < = sqrt (n)

while (s <= sqrt(N)) {

Much slower than

int limit = sqrt(N);
while (s <= limit) {

But overall, Eiko's comments are correct If you want people to provide low - level optimizations, you have to provide code

Updated, now about your code

You may notice that the number of iterations in the code is slightly greater than "L" (you can put the counter in the first 'for' loop, which will only be 2-3 times larger) obviously, the complexity of your solution can not be less than o (L) (you can't be less than 'L)' iteration)

What's really useful is effective access to memory Note that the writer of this article is trying to reduce storage space, not just because of his memory greed Making compact arrays allows you to make better use of cache, thereby increasing speed

I just replaced Boolean [] with int [] and immediately gained x2 speed gain (and 8x memory) I didn't even try to do it effectively

Update2 this is simple You only need [I / 32] | = 1 < < to replace each assignment a [i] = true (i2) and each read operation a [i] and (a [I / 32] & (1 < (i2)))= 0. And Boolean [] A and int [] A, obviously From the first replacement, it should be clear how it works: if f (I) is true, then bit 1 in integer a [I / 32] and bit I2 (int in Java happens to be 32 bits, as you know) You can go further and replace I / 32, 5, I2 and I & 31 with I > > You can also pre calculate all 1 < < J for each J between 0 and 31 in the array. Unfortunately, I don't think you can get close to C in Java. Not to mention that guy uses many other tricky optimizations. I agree that if he comments, his value may be higher