DEV Community

Peter Kim Frank
Peter Kim Frank Subscriber

Posted on

Project Euler #7 - 10001st prime

Continuing the wonderful community solutions to Project Euler.

This is Problem 7, 10001st prime.

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 10,001st prime number?

Top comments (12)

Collapse
 
peter profile image
Peter Kim Frank

Hey, I want to make sure we're following their rules and guidelines. I had reviewed the copyright page (and the related license) and I was confident we were following their preferred attribution requests and other specifications.

Can you point me in the right direction here if I'm missing something?

Collapse
 
gcvancouver profile image
gcacher • Edited

Read through their about page. They have a few points addressing sharing questions & solutions. Specifically, question 13 and the disclaimer at the bottom.

I know that in the past, they were "blocking" people who shared solutions online. It seems like they have realized that that is not a feasible goal, but it is still important to respect their objectives.

Collapse
 
flrnd profile image
Florian Rand • Edited

Found it!

I learned so much solving problem XXX so is it okay
to publish my solution elsewhere?

It appears that you have answered your own question. There is nothing quite like that "Aha!" moment when you finally beat a problem which you have been working on for some time. It is often through the best of intentions in wishing to share our insights so that others can enjoy that moment too. Sadly, however, that will not be the case for your readers. Real learning is an active process and seeing how it is done is a long way from experiencing that epiphany of discovery. Please do not deny others what you have so richly valued yourself.

Thread Thread
 
peter profile image
Peter Kim Frank

Thanks for this. The "logged-out" version of the page wasn't showing this question+answer for some reason.

In recognition of this preferred policy, I'll discontinue the series here on DEV.

Thanks to you, @brandelune , and @gcvancouver for making me aware of this policy. I'll start posting questions from a different source in the coming days.

Collapse
 
karataev profile image
Eugene Karataev • Edited

JS

function getPrimes(max) {
  let arr = new Array(max).fill(undefined);
  for (let i = 2; i < max; i++) {
    if (arr[i] === undefined) {
      arr[i] = true;
      for (let j = i + i; j < max; j += i) {
        arr[j] = false;
      }
    }
  }
  return arr
    .map((item, i) => item ? i : false)
    .filter(Boolean)
}

let primes = getPrimes(150000);
console.log(primes[10000]);
Collapse
 
maxart2501 profile image
Massimo Artizzu • Edited

JavaScript:

const primes = [ 2, 3 ];
function isPrime(n) {
  return primes.every(d => n % d > 0);
}

let i = 1;
while (primes.length < 10001) {
  const n = i * 3 + 1.5 + .5 * (-1) ** (i + 1);
  if (isPrime(n)) primes.push(n);
  i++;
}
console.log(primes[10000]); 

If some is wondering what in the world I'm doing to compute n, it's about this: every prime number larger than 3 is of the form 6 k Β± 1. With a little manipulation it could be rewritten as 3/2 + 3 h + (-1)h + 1 / 2.

Collapse
 
aspittel profile image
Ali Spittel

Python

def is_prime(n):
    nums_to_check = range(2, int(n**.5) + 1)
    for i in nums_to_check:
        if n % i == 0:
            return False
    return True

def prime_at_index(idx):
    n_primes = 1
    n = 2
    while n_primes < idx:
        n+=1
        if is_prime(n):
            n_primes += 1
    return n

print(prime_at_index(10001))
Collapse
 
flrnd profile image
Florian Rand

Using sieve of Eratosthenes method

package main

import (
    "fmt"
    "math"
)

func primeEratosthenes(a []bool, n int) []bool {
    for i := 2; i < int(math.Sqrt(float64(n))); i++ {
        if a[i] {
            for j := i * i; j < n; j += i {
                a[j] = false
            }
        }
    }
    return a
}

func main() {
    a := make([]bool, n+1)
    for i := range a {
        a[i] = true
    }

    primes := primeEratosthenes(a, 100000)
    var pList []int

    for i, v := range primes {
        if v {
            pList = append(pList, i)
        }
    }
    pList = pList[2:]
    fmt.Println(pList[10000])
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
moose profile image
moose

class Sieve {
val magicnum: Int = 10001
fun buildSieve(startNumber: Int = 1, endNumber: Int = 100000): ArrayList {
var map = arrayListOf(NumObjects("na", 0))
for (i in startNumber..endNumber) {
map.add(NumObjects("na", i))
}
return map
}

fun doIncrement(iteration: Int, array:ArrayList<NumObjects>):ArrayList<NumObjects>{
    for(i in iteration..array.size step iteration){
        if(i+ iteration > array.size) {
            break;
        }
        array[i].hit="hit"
    }
    return array
}
fun doSieve(): Int {
    var sieveArray = buildSieve()
    val iterators: Array<Int> = arrayOf(2, 3, 5, 7)
    iterators.forEach {
        sieveArray = doIncrement(it, sieveArray)
    }
    var aff = sieveArray.filter{s-> s.hit == "na"}
    println(aff.get(ass.size-1).num)
    return aff.elementAt(magicnum-1).num
}
Enter fullscreen mode Exit fullscreen mode

}
class NumObjects(hit:String,num:Int){
var hit: String = hit
var num: Int = num
}

Collapse
 
jay profile image
Jay • Edited

Rust Solution: Playground

Got it to 17s, from 34s using the lazy iterators, was still using 2..(n/2) for checking primes.
Got it down to 0.9s by changing the prime check to 2..(sqrt(n)+1)

The iterator for checking prime uses any(|i| n % i == 0) instead of all(|i| !n % i == 0), so that it may short-circuit when any case returns true. Similar to using a loop with break condition.

Still is a brute force technique.


fn main() {
    println!("{}", get_nth_prime(10001));
}

fn get_nth_prime(n: usize) -> u32 {
    (1..).into_iter().filter(|&num| is_prime(num)).nth(n - 1).unwrap_or_default()
}

fn is_prime(n: u32) -> bool {
    match n {
        1 => false,
        2 => true,
        n if n % 2 == 0 => false,
        _ => !(2..(n as f32).sqrt() as u32 + 1).any(|i| n % i == 0),
    }
}
Collapse
 
crownedprinz profile image
Ademola John

Here is a javascript solution


function nthPrime(n) {
    let primes = [2];
    let higherDivisorLimit;
    let isPrime;
    for(let i = 3; primes.length < n; i+=2) {
      higherDivisorLimit = Math.sqrt(i) + 1;
      isPrime = true;
      for(let j = 0; primes[j] < higherDivisorLimit; j++) {
        if(i % primes[j] === 0) {
          isPrime = false;
          break;
        }
      }
      if(isPrime) primes.push(i);
    }
    return primes[primes.length - 1];
}

console.log(nthPrime(10001));
Collapse
 
nilzoft profile image
nilzoft • Edited

My solutions in .C

github/nilzoft