Java solution to Project Euler Problem 7

Problem 7:

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");
	}	
}

4 thoughts on “Java solution to Project Euler Problem 7

  1. for 10001st prime the answer is increase by 1 .. hence System.out.println(i-1) is correct

  2. 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"); } }

  3. 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;

    }

Leave a Reply

Your email address will not be published.