I have been working on this for a while now and cant seem to figure it out. This
ID: 3745556 • Letter: I
Question
I have been working on this for a while now and cant seem to figure it out.
This is what I have so far, which I thought was right and done.
public class Lab2b
{
public static int[] primes = null;
public static boolean isPrime(int n)
{
if(primes[0] == 0)
{
int root = (int) Math.sqrt(n);
for (int i=2; i<=root; i++)
{
if ((n%i) == 0)
{
return false;
}
}
return true;
}
else
{
int root = (int) Math.sqrt(n);
int i = 2;
int index = 0;
while(i<=root) {
if ((n%i) == 0)
{
return false;
}
i = primes[index];
index++;
}
return true;
}
}
public static void main(String args[])
{
primes = new int[1000000];
//Set all of them to 0
for(int i = 0; i < 1000000; i++) {
primes[i] = 0;
}
int c=0;
long start, end, mstime;
final int LIMIT=1000000; // 1M took ~800 secs.
start = System.currentTimeMillis();
for (int n=1; n<=LIMIT; n++)
{
if (isPrime(n))
{
System.out.println(n);
primes[c] = n;
c++;
}
}
end = System.currentTimeMillis();
mstime = end - start;
System.out.println("#primes = " + c + ", mstime = " + mstime);
c = 0;
start = System.currentTimeMillis();
for (int n=1; n<=LIMIT; n++)
{
if (isPrime(n))
{
c++;
}
}
end = System.currentTimeMillis();
mstime = end - start;
System.out.println("#primes(prime method) = " + c + ", mstime = " + mstime);
}
}
When I asked to check my program, this is what the instructor told me. "In your isPrime method, if you look at the code that does the division: if ((n%i) == 0) . Note that you are dividing by 'i' . You need to divide by an element from your primes array! Also note that your program, as written, only finds three prime numbers!"
I am lost, tired, and frustrated if anyone could help. Please and Thank you.
Explanation / Answer
In the else case of isPrime function in the while loop you are trying to divide with each element in the prime array instead of that try to increment i in the while loop.
while(i<=root) {
if ((n%i) == 0)
{
return false;
}
i++ //instead of dividing with elements in the prime array increment i
// i = primes[index]; //instead of dividing with elements in the prime array increment i
//index++; //instead of dividing with elements in the prime array increment i
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.