##Ways to decrease the allocation##
Ways to decrease the allocation
Since your main question was about the allocation length, I'll suggest two ways to decrease the allocation (although 1 MB really isn't that much to begin with).
Since the only even number that is prime is 2, you can only allocate half the amount by only considering odd numbers. When you perform the sieve, you skip all even numbers and use index
[j/2]for each odd number. Just remember at the end to count 2 as one of the primes if the range includes it.You can use 1 bit per number instead of 1 boolean per number. You can use
BitSetor your own bit array.
Combining both of the above allows you to allocate 1/16 the amount that you originally allocated (so about 64KB instead of 1MB). I don't think it will help at all though. If anything, your program will only get slower.
##Reuse the allocation##
Reuse the allocation
Also, since you are running up to 100 test cases, you might as well just run the sieve once on the maximum input (10^6). Then you can compute the 100 answers quickly without redoing all the work each time.
##Ways to decrease the allocation##
Since your main question was about the allocation length, I'll suggest two ways to decrease the allocation (although 1 MB really isn't that much to begin with).
Since the only even number that is prime is 2, you can only allocate half the amount by only considering odd numbers. When you perform the sieve, you skip all even numbers and use index
[j/2]for each odd number. Just remember at the end to count 2 as one of the primes if the range includes it.You can use 1 bit per number instead of 1 boolean per number. You can use
BitSetor your own bit array.
Combining both of the above allows you to allocate 1/16 the amount that you originally allocated (so about 64KB instead of 1MB). I don't think it will help at all though. If anything, your program will only get slower.
##Reuse the allocation##
Also, since you are running up to 100 test cases, you might as well just run the sieve once on the maximum input (10^6). Then you can compute the 100 answers quickly without redoing all the work each time.
Ways to decrease the allocation
Since your main question was about the allocation length, I'll suggest two ways to decrease the allocation (although 1 MB really isn't that much to begin with).
Since the only even number that is prime is 2, you can only allocate half the amount by only considering odd numbers. When you perform the sieve, you skip all even numbers and use index
[j/2]for each odd number. Just remember at the end to count 2 as one of the primes if the range includes it.You can use 1 bit per number instead of 1 boolean per number. You can use
BitSetor your own bit array.
Combining both of the above allows you to allocate 1/16 the amount that you originally allocated (so about 64KB instead of 1MB). I don't think it will help at all though. If anything, your program will only get slower.
Reuse the allocation
Also, since you are running up to 100 test cases, you might as well just run the sieve once on the maximum input (10^6). Then you can compute the 100 answers quickly without redoing all the work each time.
##Ways to decrease the allocation##
Since your main question was about the allocation length, I'll suggest two ways to decrease the allocation (although 1 MB really isn't that much to begin with).
Since the only even number that is prime is 2, you can only allocate half the amount by only considering odd numbers. When you perform the sieve, you skip all even numbers and use index
[j/2]for each odd number. Just remember at the end to count 2 as one of the primes if the range includes it.You can use 1 bit per number instead of 1 boolean per number. You can use
BitSetor your own bit array.
Combining both of the above allows you to allocate 1/16 the amount that you originally allocated (so about 64KB instead of 1MB). I don't think it will help at all though. If anything, your program will only get slower.
##Reuse the allocation##
Also, since you are running up to 100 test cases, you might as well just run the sieve once on the maximum input (10^6). Then you can compute the 100 answers quickly without redoing all the work each time.