We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #7: 10001st prime
  4. Discussions

Project Euler #7: 10001st prime

Sort by

recency

|

268 Discussions

|

  • javlonsaipov
     + 3 comments
    import sys
import math

t = int(input().strip())
for a0 in range(t):
    n = int(input().strip())
    if n<=10**5 and n>=1:
        vb=0
        b=2
        while vb!=n:
            sr=0
            for i in range(2,int(math.sqrt(b))+1):
                if b%i==0:
                    sr=1
                    break
            if sr==0:
                vb+=1
            b+=1
        print(b-1)

  • fakedgrid
     + 0 comments

    here is my fastest implementation of this in python using sieve of atkin:

    import math

def sieve_of_atkin(limit):
    sieve = [False] * (limit + 1)
    sieve[2], sieve[3] = True, True
    
    for x in range(1, int(math.sqrt(limit)) + 1):
        for y in range(1, int(math.sqrt(limit)) + 1):
            n = 4 * x**2 + y**2
            if n <= limit and (n % 12 == 1 or n % 12 == 5):
                sieve[n] = not sieve[n]
            
            n = 3 * x**2 + y**2
            if n <= limit and n % 12 == 7:
                sieve[n] = not sieve[n]
            
            n = 3 * x**2 - y**2
            if x > y and n <= limit and n % 12 == 11:
                sieve[n] = not sieve[n]

    for x in range(5, int(math.sqrt(limit)) + 1):
        if sieve[x]:
            for y in range(x**2, limit + 1, x**2):
                sieve[y] = False
    
    return sieve

def count_primes(sieve):
    return [i for i in range(2, len(sieve)) if sieve[i]]

def nth_prime_fast(n):
    if n < 1:
        return None
    if n == 1:
        return 2
    
    limit = max(10, n * int(math.log(n) + math.log(math.log(n))))
    while True:
        sieve = sieve_of_atkin(limit)
        primes = count_primes(sieve)
        if len(primes) >= n:
            return primes[n - 1]
        limit *= 2


print(nth_prime_fast(10001))

  • tjmfollosco
     + 0 comments

    Woah. That was easier than I thought. I don't know maybe it's because my solution is simple. C# solution

    1. I get the list of primes for the first 10000.
    2. Just put.
    public static void getPrimes(List<int> Primes)
    {
        for(int i = 3; Primes.Count <= 10000; i+=2)
        {
            bool isPrime = true;
            if(i == 3) {Primes.Add(3);}
            foreach(int prime in Primes)
            {
                if( i % prime == 0)
                {
                    isPrime = false;
                    break;
                }
            }
            if(isPrime)
            {
                Primes.Add(i);
            }
        }
    }

static void Main(String[] args) {
        int t = Convert.ToInt32(Console.ReadLine());
        //get primes
        List<int> Primes = new List<int>();
        Primes.Add(2);
        //add the primes to the list
        myFunc.getPrimes(Primes);
        for(int a0 = 0; a0 < t; a0++){
            int n = Convert.ToInt32(Console.ReadLine());
            Console.WriteLine(Primes[n-1]);
        }
    }

  • ishwardharme320
     + 0 comments

    Java

    public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    List<Integer> list=new ArrayList<>();
    int t = in.nextInt();
    for(int a0 = 0; a0 < t; a0++){
        int n = in.nextInt();
        list.add(n);
    }
    int max=list.stream().max(Integer::compare).orElse(0);

    Map<Integer,Integer> map= new LinkedHashMap<>();
    int count;
    int x=0;
    int i=2;
    while(x<=max){
        count=0;
        for(int j=2;j<=i/2;j++){
            if(i%j==0 ){
             count++;
                break;
            }else{
                continue;
            }
        }
        if(count==0){
            x++;
           map.put(x, i); 
        } 
        i++;
    }
    for(int k=0;k<list.size();k++){
        System.out.println(map.get(list.get(k)));
    }
}

  • burham
     + 0 comments

    Solution in JavaScript:

    Create array of 10001 primes once before starting the loop, then get N from array's index

    /////////////// ignore above this line ////////////////////

function main() {
  var t = parseInt(readLine());
  let primesArr = []
  let i = 2
  while (primesArr.length <= 10000) {
    if (isPrime(i) && !primesArr.includes(i)) primesArr.push(i)
    if (Number(primesArr.length) <= 10000) i++
    else break
  }
  for (var a0 = 0; a0 < t; a0++) {
    var n = parseInt(readLine());
        console.log(primesArr[Math.floor(n)-1])
  }
}
function isPrime(n) {
  if (n < 2) return false
  let sqrt = Math.floor(Math.sqrt(n))
  for (let i = 2; i <= sqrt; i++) {
    if (n % i == 0) return false
  }
  return true
}