I\'m trying to implement the Sieve of Eratosthenes to find the prime numbers bet
ID: 3886072 • Letter: I
Question
I'm trying to implement the Sieve of Eratosthenes to find the prime numbers between 2 and 1,000,000
For this program, you will need to initialize the "sieve"
before you begin making the calls to "isPrime()". Implement
the sieve in an "init()" method that is called by main.
This will allow your main method to remain otherwise unchanged
from the sample main methods I provided. Make sure thatyour
call to "init()" is inside your calls that measure the runtime.
This is what I've been working on:
public class Lab3
{
static boolean[] primes;
public static void initSieve(int n)
{
//Sets all elements in array to true
for(int i = 0; i <= n; i++){
primes[i] = true;
}
//Fill the arrays non-prime numbers to false using sieve method
final int lim = (int)Math.sqrt(n);
for (int i=2; i*i <= lim; i++){
if (primes[i] == true) {
for (int j= i+i; j<= n; j++){
primes[j] = false;
}
}
}
}
public static boolean isPrime(int n){
return primes[n];
}
public static void main(String args[])
{
int c = 0;
long start, end, mstime;
final int LIMIT=1000000;
start = System.currentTimeMillis();
initSieve(LIMIT);
primes = new boolean[LIMIT];
primes[0] = primes[1] = false;
for (int i=2; i<LIMIT; i++) {
if (isPrime(i))
{
System.out.println(i);
c++;
}
}
end = System.currentTimeMillis();
mstime = end - start;
System.out.println("#primes = " + c + ", mstime = " + mstime);
}
}
Explanation / Answer
Hi Friend, I have fixed all the issue and program is working correctly.
public class Lab3
{
static boolean[] primes;
public static void initSieve(int n)
{
//Sets all elements in array to true
for(int i = 2; i <= n; i++){
primes[i] = true;
}
//Fill the arrays non-prime numbers to false using sieve method
for(int p = 2; p*p <=n; p++)
{
// If prime[p] is not changed, then it is a prime
if(primes[p] == true)
{
// Update all multiples of p
for(int i = p*2; i <= n; i += p)
primes[i] = false;
}
}
}
public static boolean isPrime(int n){
return primes[n];
}
public static void main(String args[])
{
int c = 0;
long start, end, mstime;
final int LIMIT=1000000;
start = System.currentTimeMillis();
primes = new boolean[LIMIT+1];
primes[0] = primes[1] = false;
initSieve(LIMIT);
for (int i=2; i<LIMIT; i++) {
if (isPrime(i))
{
System.out.println(i);
c++;
}
}
end = System.currentTimeMillis();
mstime = end - start;
System.out.println("#primes = " + c + ", mstime = " + mstime);
}
}