By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10001st prime number?
Running time: 10010ms (10 sec)
Assessment: This is a classic example of a bad factorization algorithm, because the results aren’t memoized in any way. I promise my solutions get a lot better right around Problem 21.
public class Problem007 { private static boolean isPrime(long n) { //returns 0 if not prime, 1 if prime if ((n % 2 == 0)&&(n != 2)) return false; // is even, therefore not prime for (long i = 3; i <= (n^(1/2)+1); i += 2) // Skip all the even numbers { if (n % i == 0) return false; //not prime } return true; } public static void main(String[] args) { long begin = System.currentTimeMillis(); int NumPrimes = 1; long i = 2; while(NumPrimes <= 10001) { if (isPrime(i)) { i++; NumPrimes++; } else i++; } long end = System.currentTimeMillis(); System.out.println(i); System.out.println(end-begin + "ms"); } }
for 10001st prime the answer is increase by 1 .. hence System.out.println(i-1) is correct
for less complexity you can use
public class Problem7{ private static boolean isPrime(long n){ if(n%2==0&&n!=2) return false; for(long i=3;i<=Math.sqrt(n)+1;i+=2){ if(n%i==0) return false; } return true; } public static void main(String[] args){ long begin=System.currentTimeMillis(); int NumPrimes=2; long i=3; while(NumPrimes<=10001){ if(isPrime(i)){ i+=2; NumPrimes++; } else i+=2; } long end = System.currentTimeMillis(); System.out.println(i-2); System.out.println(end-begin + "ms"); } }
why use math.sqrt(n) in for loop?
ther is a small error in this code …instead of stopping at PRIME NO. 10001 ..the while loop run one time more than the required..
So to get the accurate answer ..plz put this line of code in “if(isPrime(i))”
”
if(NumPrimes==10001)
{
System.out.println(i);
break;
}
“