Prime Product Problem

Computer Science Level 4

$\{p_1,p_2,p_3,\ldots,p_n,\ldots\}$ is the set of primes. $f(n)=\prod_{i=1}^np_i$ What are the last three digits of $f(2014)\text{?}$

The answer is 330.

3 solutions

Thaddeus Abiy
Jan 15, 2014

Visual Sieve of Erastothenes

I used the sieve of Eratosthenes to generate all the primes below $10^5$ .I then computed every product modulo $10^3$ just to keep track of the last three digits. A visual explanation of the Sieve is given above.

Answer = 1
for i,pi in enumerate(primesbelow(10**5)):
    if i == 2014:break
    Answer *= pi ; Answer %= 1000
print Answer

The sieve can be implemented easily but this snippet from stackoverflow is the fastest version I know of.

def primesbelow(N):
         # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
         #""" Input N>=6, Returns a list of primes, 2 <= p < N """
         correction = N % 6 > 1
         N = {0:N, 1:N-1, 2:N+4, 3:N+3, 4:N+2, 5:N+1}[N%6]
         sieve = [True] * (N // 3)
         sieve[0] = False
         for i in range(int(N ** .5) // 3 + 1):
             if sieve[i]:
                 k = (3 * i + 1) | 1
                 sieve[k*k // 3::2*k] = [False] * ((N//6 - (k*k)//6 - 1)//k + 1)
                 sieve[(k*k + 4*k - 2*k*(i%2)) // 3::2*k] = [False] * ((N // 6 - (k*k + 4*k - 2*k*(i%2))//6 - 1) // k + 1)
         return [2, 3] + [(3 * i + 1) | 1 for i in range(1, N//3 - correction) if sieve[i]]

Image Source:Wikipedia commons

Thaddeus Abiy - 7 years, 4 months ago

Really I don't think a solution exists without programming here. This question should have been posted in Computer Science.

A Brilliant Member - 7 years, 4 months ago

Yes I think so too,Isnt this a CS problem?

Thaddeus Abiy - 7 years, 4 months ago

It is a Comp Sci problem. I put tags on it that would indicate so, but those aren't showing up for now. Logan Dymond made a post requesting the ability to classify problems, and the Brilliant staff said that is something they are working on.

Trevor B. - 7 years, 4 months ago

You can also make a prime array prime with some starting primes and then adding primes to it after testing the next number (using a for loop) for primality by trial division from prime[0] to prime[k] where prime[k] $\leq\left\lfloor\sqrt n\right\rfloor$ ( $n$ is the number being tested). If $n$ is prime, it's added to the array. Keeping count, we do this till we get $2014$ primes in prime and then it's simple modular calculation.

Here 's my C++ implementation of the above idea (runs in 0.14 sec).

Although, maybe this is equivalent to using Sieve of Eratosthenes if we compare execution time (?).

Prasun Biswas - 5 years, 10 months ago

Yes, that method is also equally valid. The Sieve is slightly superior because it runs in $O(nlog(log(n)))$ time. I think the trial division approach can be bound by $\sqrt{1}+\sqrt{2}+\sqrt{3}..\sqrt{n} < \int_{k=0}^{n}{x^{0.5} }= O(n^{1.5})$ . The trial division method can be refined to faster non-deterministic tests like miller rabin .

Thaddeus Abiy - 5 years, 10 months ago

Edward Jiang
Sep 22, 2014

No way to solve this except brute force, so that's what I did, hehe. Here's the PARI/GP program:

(prod(k=1,2014,prime(k)))%1000

PARI/GP strikes again, you are the man ^^

Elmokhtar Mohamed Moussa - 6 years, 3 months ago

Hjalmar Orellana Soto
Feb 25, 2016

a=1
b=0
c=1
while b<2014:
    d=2
    while d<a:
        if a%d==0:
            d+=a
        else:
            d+=1
    if a==d:
        b+=1
        c*=a
    a+=1
print int(str(c)[len(str(c))-3]+str(c)[len(str(c))-2]+str(c)[len(str(c))-1])

Prime Product Problem

The answer is 330.

3 solutions

0 pending reports