Question

Find the first 100 primes found by the classical proof of the infinitude of the set of primes. That is: begin with P={2}; then form m, the sum of 1 with the product over all elements of P. Place the smallest prime factor of m into P and repeat. (For this problem, you may use FactorIntegeror similar built-in Mathematica functions.). Produce a Mathematica procedure with the above instructions.

Answer 1

First We should know what is classical proof of the infinitude of the set of primes. It is a proof of existence of infinite prime numbers.

Euclid's Proof

Let's assume there are p primes p1,p2,p3.......pk.

Assume a number M= p1*p2*p3*.......*pk+1

when M is divided by any of the primes it gives remainder 1 thus it violates Fundamental theorem of Arithmetic.

Hence our assumption is wrong and there are infinite prime numbers.

Now lets come to ques p={2} m=3 -> P{2,3} m=7 -> P(2,3,7)

Pseudocode;

x=2

m=2

While(p.size()<=100){

x=m+1

arr[]=Integer.factor(x)

p.add(arr[0]) //here arr[0] denotes the smallest prime factor of x

m=m*arr[0]

}

By this you get the first 100 primes in array P.