# Project Euler #7: 10001st prime

# Project Euler #7: 10001st prime

Kartik1607 + 0 comments Anyone else who cried after solving this? I tried to solve this for 2 hours. Time out. Always.

So, I tried to use dyanmic stack in CPP to store already found even numbers... Still the last one gave me timeout.

Solution ?

`1) Add 2 and 3 to stack. 2) If n <= Size of stack, get item at position n and output answer 3) Else, start from last element of stack, check if prime 4) To check for prime, recursively divide from each element in stack. If remainder 0 for any element in stack, not a prime. Break loop 5) If Prime, add to stack 6) Search only odd numbers`

That's it. Now the last one which always timed out gave result in 0.3 seconds.

shanker4999 + 0 comments I pre computed all the prime number.

public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); int t = in.nextInt(); int[] prime = new int[10000]; prime[0]=2; int k=1; int i=3; int count =1; while(count<10000){ boolean flag = true; for(int j=3;j<i/2;j++){ if(i%j==0){ flag = false; break; } } if(flag==true){ prime[k]=i; count++; k++; } i=i+2; } for(int a0 = 0; a0 < t; a0++){ int n = in.nextInt(); System.out.println(prime[n-1]); } } }

tanejaswapnil + 0 comments My code worked only after changing the size of sieve. I increased it's size from 10001 to 200000. See if it works for any of you guys too. But, I don't know why TLE was shown before changing size - when it should have shown error ? This is weird.

elmartins + 0 comments In Ruby 1.9 there is a Prime class you can use to generate prime numbers.

request 'prime' Prime.take(10) # => [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

asbear + 0 comments I tend not to use external math formula because I am crap at math and I cannot google during the job interview. I see mentioning checking prefect square or Sieve method in the discussion comments. However I wrote simple code without those things and it passed the test easily. Here is what I considered to avoid timeout.

I used a list of prime numbers which is topped up on demand. Therefore prime number chekcing is performed only once per number. For this I add fillPrimes(nth) and call it when N exceeds the size of the list.

Plus, my isPrime() function uses sqrt() for the check. This is fundamental knowledge but very important for this kind of quiz. Otherwise you could be stuck in timeout.

skip even number. Small saving :)

Sort 195 Discussions, By:

Please Login in order to post a comment