Project Euler/7

← Back to User:ProjectEuler

Project Euler Problem 7 is a problem related to prime numbers. It requires you to find the 10001st prime number.

This article is not detailed enough and needs to be expanded. Please help us by adding some more information.

Implementations

Aheui

This may theoretically work, but it is very ineffective. It even failed on Try It Online.

박싹밤발발따따빠따발발나다뿌서더너벌벌석터너벌벌머차삭빠사빠싹삭루
수ㅇㅇㅇㅇㅇ희멍터너벌벌석차박빠삭빠싸사타야ㅇ야ㅇ오두ㅇ너벌벌서처
마ㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇ야오야여요뼈ㅇㅇㅇㅇㅇ어

Second try that also fails:

방박싹사뿌서
누벌벌석차박싼산빠빠따삭빠산싹삭주
타망희ㅇㅇ요나도ㅇ루석썩뻐선뻐석처산마수
ㅇㅇㅇㅇㅇㅇ볼벌선처산마숙ㅇㅇㅇ터너벌벌
ㅇㅇㅇㅇㅇ오ㅇㅇㅇ더너벌벌

Third attempt based on the C program below, and it still fails:

방박싹사뿌서
너벌벌석차ㅣ아순머희멍터
ㅇㅇㅇㅇㅇㅇ우빠쏞
ㅇㅇㅇ우ㅇㅇ삲뺘아빠따삭빠삲싹삭주
ㅇㅇㅇ어ㅇㅇ쏜ㅇㅇ루석썩뻐섢뻐석처수
ㅇㅇㅇㅇㅇㅇ솒ㅇㅇ처숙어마숞터너벌벌
ㅇㅇㅇㅇㅇ숀ㅇ더너벌벌ㅇ쏜뻐숙
ㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇ쏜ㅇㅇ뻐

There may be an alternative that uses the queue.

Fourth attempt by User:Miui

반받따받따밞반다따밞반따발다따밞반따발다따반반나다망희

verify here

C

This program works on Try It Online.

#include <stdio.h>
int e[10002]={0},i=0,ei=0;
int a=2;
int c=10001;
int main(){
for(a=2;c>0;++a){
 if(ei==0){e[ei]=a;++ei;--c;}
 else{
  for(i=0;e[i]*e[i]<=a;++i){
   if(a%e[i]==0){break;}
  }
  if(a%e[i]!=0){e[ei]=a;++ei;--c;}
 }
}
printf("%d",a-1);
return 0;
}

C++

#include <bits/stdc++.h>

using namespace std;

// Estimate an upper bound for the n-th prime (n >= 6)
size_t estimate_bound(size_t n) {
    if (n < 6) return 15; // safe for n=1..5
    double log_n = log(n);
    double log_log_n = log(log_n);
    // Add a safety margin of 10
    return static_cast<size_t>(n * (log_n + log_log_n)) + 10;
}

// Return the n-th prime (1-indexed)
size_t nth_prime(size_t n) {
    if (n == 0) throw invalid_argument("n must be positive");
    if (n == 1) return 2;
    if (n == 2) return 3;

    size_t limit = estimate_bound(n);

    // Sieve of Eratosthenes using a vector<char> (faster than vector<bool>)
    vector<char> is_prime(limit + 1, true);
    is_prime[0] = is_prime[1] = false;

    size_t sqrt_limit = static_cast<size_t>(sqrt(limit));
    for (size_t i = 2; i <= sqrt_limit; ++i) {
        if (is_prime[i]) {
            for (size_t j = i * i; j <= limit; j += i)
                is_prime[j] = false;
        }
    }

    // Count primes until we reach the n-th
    size_t count = 0;
    for (size_t p = 2; p <= limit; ++p) {
        if (is_prime[p]) {
            ++count;
            if (count == n) return p;
        }
    }

    // Fallback: if the bound was too small (rare), continue with trial division
    size_t candidate = limit + 1;
    while (true) {
        bool prime = true;
        for (size_t d = 2; d * d <= candidate; ++d) {
            if (candidate % d == 0) {
                prime = false;
                break;
            }
        }
        if (prime) {
            ++count;
            if (count == n) return candidate;
        }
        ++candidate;
    }
}

int main() {
    size_t n = 10001;

    try {
        size_t result = nth_prime(n);
        cout << "The " << n << "-th prime number is " << result << "." << endl;
    } catch (const exception& e) {
        cerr << "Error: " << e.what() << endl;
        return 1;
    }

    return 0;
}

Lua

-- Estimate an upper bound for the n-th prime (n >= 6)
local function estimate_bound(n)
    if n < 6 then return 15 end
    local log_n = math.log(n)
    local log_log_n = math.log(log_n)
    return math.floor(n * (log_n + log_log_n)) + 10
end

-- Return the n-th prime (1-indexed)
local function nth_prime(n)
    if type(n) ~= "number" or n < 1 or n ~= math.floor(n) then
        error("n must be a positive integer")
    end
    if n == 1 then return 2 end
    if n == 2 then return 3 end

    local limit = estimate_bound(n)

    -- Sieve of Eratosthenes using a Lua table (boolean values)
    local is_prime = {}
    for i = 0, limit do is_prime[i] = true end
    is_prime[0] = false
    is_prime[1] = false

    local sqrt_limit = math.floor(math.sqrt(limit))
    for i = 2, sqrt_limit do
        if is_prime[i] then
            for j = i * i, limit, i do
                is_prime[j] = false
            end
        end
    end

    -- Count primes
    local count = 0
    for p = 2, limit do
        if is_prime[p] then
            count = count + 1
            if count == n then return p end
        end
    end

    -- Fallback: if bound was too small, continue with trial division
    local candidate = limit + 1
    while true do
        local prime = true
        local d = 2
        while d * d <= candidate do
            if candidate % d == 0 then
                prime = false
                break
            end
            d = d + 1
        end
        if prime then
            count = count + 1
            if count == n then return candidate end
        end
        candidate = candidate + 1
    end
end

-- Main

local result = nth_prime(10001)
print(result)

Python

import math
import sys

def nth_prime(n: int) -> int:
    """
    Return the n-th prime number (1-indexed).
    """
    if n <= 0:
        raise ValueError("n must be a positive integer")
    if n == 1:
        return 2
    if n == 2:
        return 3

    # Estimate an upper bound for the n-th prime.
    # For n >= 6, a safe bound is n * (log(n) + log(log(n))).
    # We add a small safety margin.
    if n >= 6:
        log_n = math.log(n)
        log_log_n = math.log(log_n)
        limit = int(n * (log_n + log_log_n)) + 10
    else:
        # Small n handled separately.
        limit = 15  # enough for n up to 5

    # Sieve of Eratosthenes up to 'limit'
    sieve = bytearray(b'\x01') * (limit + 1)
    sieve[0:2] = b'\x00\x00'  # 0 and 1 are not prime

    for i in range(2, int(limit ** 0.5) + 1):
        if sieve[i]:
            step = i
            start = i * i
            sieve[start:limit + 1:step] = b'\x00' * ((limit - start) // step + 1)

    # Extract primes and return the n-th one
    count = 0
    for p in range(2, limit + 1):
        if sieve[p]:
            count += 1
            if count == n:
                return p

    # If the bound was too small (should not happen with the above estimates),
    # fall back to a slower trial‑division generator to extend.
    # (This is rarely needed.)
    candidate = limit + 1
    while True:
        is_prime = True
        for d in range(2, int(candidate ** 0.5) + 1):
            if candidate % d == 0:
                is_prime = False
                break
        if is_prime:
            count += 1
            if count == n:
                return candidate
        candidate += 1

def main():
    result = nth_prime(10001)
    print(f"The 10001st prime number is {result}.")

if __name__ == "__main__":
    main()

A shorter version that uses brute force:

def isprime(x):
    for i in range(2,int(x**0.5)+1):
        if x%i==0:return 0
    return 1
t,r=2,0
while r<10001:
    r+=isprime(t)
    t+=1
print(t-1)

An even shorter version, but is considered cheating for it uses the sympy package directly.

print(__import__('sympy').prime(10001))

External resources

• Prime number on Wolfram Mathworld
• A000040, a related sequence on OEIS. The 10001st term is the solution.
• Problem 7 on Project Euler Official Website (not available)
• Problem 7 on Project Euler Mirror