# Who can find the largest prime number with their own programmed code?

• Python
• Kekkuli
Kekkuli
I announce a playful competition Who can find the largest prime number with the programmed code? I found the number 2249999999999999981 with the Python code. I first tabulated the truth value of the prime numerosity of numbers smaller than 1.5 billion using Erasthonene's sieve, and then I started to study numbers from 1.5*1.5 billion downwards.
Big Prime number:
import math

maxind = 1500000000  # let's calculate prime numbers smaller than 1.5 billion
primesarray = [True] * (maxind + 1)
amount = maxind
number = 0
ind = 0
squareroot = 0.0
candinate = 0
helper = 0def is_prime_number(num):
if num % 2 == 0:
return False
else:
index = 3
itis = True
while index <= math.isqrt(num) and itis:
if primesarray[index]:
if num % index == 0:
itis = False
print(index)
index += 2
return itisamount = maxind
squareroot = math.isqrt(amount)
for ind in range(2, maxind + 1):
primesarray[ind] = True  # let's suppose all are primes
primesarray[1] = False
number = 2
ind = number

while ind <= amount:
primesarray[ind] = False  # remove 2's multiplies
ind += 2

while number < squareroot:
while primesarray[number] is False and number < squareroot:
number += 1  # let's find next prime number
ind = number + number
while ind < amount:  # remove its multiplies
primesarray[ind] = False
ind += number
number += 1

primesarray[2] = True
# Prime numbers smaller than a billion have now been tabulated.
# Let's print a hundred smaller ones as a test.
for ind in range(1, 101):
if primesarray[ind]:
print(ind)

# let's examine candidate number
helper = 1
while helper < 20:
candinate = maxind * maxind - helper
if is_prime_number(candinate):
print(candinate, ' is a prime number.')
else:
print(candinate, ' is not a prime number.')
helper += 2

DeBangis21
Bash:
#!/bin/bash
wget -q -O - 'https://html.duckduckgo.com/html?q=the%20largest%20known%20prime%20number' | sed 's|<[^>]*>||g' | sed 's|\s+| |g' | grep -P 'the largest known prime number is [^a-z]+' | sed -E 's|.+(the largest known prime number is [^a-zA-Z]+).+|\1|'
Result: the largest known prime number is 2^ (82,589,933) - 1.

What do I win?

phyzguy, Tom.G, DaveE and 2 others
I found 18446744073709551557 before I overflowed 64 bits.

Baluncore said:
I found 18446744073709551557 before I overflowed 64 bits.
Thanks! That is just what I needed when I was looking for the prime factors of 340282366920938461286658806734041124249! . ;-)
CORRECTION: The '!' was meant to be an exclamation mark, not a factorial.

Last edited:
FactChecker said:
... I was looking for the prime factors of 340282366920938461286658806734041124249!
Like all factorials, that must be composite.

Baluncore said:
Like all factorials, that must be composite.
Sorry. Not a factorial. I should have ended it with a period.

We must watch these things.
An exclamation needs to be a short and immediate reaction.

Assuming a number is a square, s = n2.
The factor n will occur exactly twice in s.
But how many times will the factor n occur in s! (yes, the actual factorial) ?

Baluncore said:
Assuming a number is a square, s = n2.
The factor n will occur exactly twice in s.
But how many times will the factor n occur in s! (yes, the actual factorial) ?
##n+1## times?

Baluncore
Baluncore said:
We must watch these things.
An exclamation needs to be a short and immediate reaction.

Assuming a number is a square, s = n2.
The factor n will occur exactly twice in s.
But how many times will the factor n occur in s! (yes, the actual factorial) ?
It depends whether ##n## is prime. Otherwise, you could get a factor of 10, say, from 2 times 5.

Baluncore
PeroK said:
It depends whether n is prime. Otherwise, you could get a factor of 10, say, from 2 times 5.
So the count would increase.
Does it get any easier if you reduce s! to its prime factors ?
If n was prime, there would be n+1 occurrences.
If n was composite, there would be zero occurrences.

Baluncore said:
If n was prime, there would be n+1 occurrences.
If n was composite, there would be zero occurrences.
If ##n## is composite, it gets complicated!

PeroK said:
If n is composite, it gets complicated!
What is the factorial of complicated ?

Another related mental exercise.
Under what conditions can a factorial also be a perfect square ?

Baluncore said:
Under what conditions can a factorial also be a perfect square ?
Never, except the trivial case of 1. This is because you would need even powers of every prime factor, but you always have an odd power of the last prime in the factorial.

PeroK said:
Never, except the trivial case of 1
Or zero.

Baluncore
Or zero.
##0! =1##

pinball1970
PeroK said:
Never, except the trivial case of 1. This is because you would need even powers of every prime factor, but you always have an odd power of the last prime in the factorial.
A full proof based on this observation requires Bertrand's postulate:

https://en.m.wikipedia.org/wiki/Bertrand's_postulate

Last edited:
PeroK said:
0! =1
Yes, and 0! is exactly as much of a perfect square as 1!, no?

Baluncore
Kekkuli said:
Who can find the largest prime number with the programmed code?
My reaction is, who cares? It's going to depend on how powerful a computer you can run it on, as much as the algorithm (as @Baluncore showed in post #3) and someone is always going to have a bigger and faster computer.

MatinSAR, Khi Choy Xichdu and Frabjous
Yes, and 0! is exactly as much of a perfect square as 1!, no?
They are the same perfect square.

Why yes. Yes they are.

phinds said:
... and someone is always going to have a bigger and faster computer.
With only one exception, the one with the biggest computer.

Baluncore said:
With only one exception, the one with the biggest computer.
Until it isn't any more

Khi Choy Xichdu
The best known way to find large primes is the lucas-lehmer test for mersenne primes (primes of the form 2^p-1 where p is a prime).
This is actually quite simple to do
Python:
# returns True if  2**p -1 is a mersenne prime, false otherwise
# assumes p is prime

def is_mersenneprime(p):
if p==2:
return True
mp = 2**p -1
m = 4
for _ in range(p-2):
m = (m*m-2) % mp

return (m==0)

python has unlimited integers and I believe uses Karatsuba multiplication, so this should run in O(p^3.58)
running this for p<1000 <1 second
running this for p<10000 14 minutes
running this for p<10^8 10^9 years.
you should really install mpz at this point, to use FFT multiplication and O(p^3) time

Of course the GIMPS project has been at this since 1996 with ~10^5 cpu cores, so it's rather hard to get ahead of this.
https://www.mersenne.org/

So wouldn’t 2^18446744073709551557 -1 also be prime?

BWV said:
So wouldn’t 2^18446744073709551557 -1 also be prime?
Why do you think that?

pbuk said:
Why do you think that?
Misremembering Mersenne primes, somehow thought 2^prime -1 was also prime

With Mersenne primes 2^p-1, p is indeed always prime, but the opposite does not necessarily hold true. Large Mersenne primes occur rather sparsely, the biggest tested so far is 2^82589933 - 1. So, some way to go until we know.

BWV
Still waiting on my code to finish running, but sure its going to be a winner

for i=82,589,933:1,000,000,000
X(i)=[(2^i)-1*isprime(2^i)-1]
end
max(X)

;)

• Programming and Computer Science
Replies
36
Views
3K
• Programming and Computer Science
Replies
34
Views
3K
• Programming and Computer Science
Replies
7
Views
1K
• Programming and Computer Science
Replies
13
Views
1K
• Programming and Computer Science
Replies
16
Views
1K
• Programming and Computer Science
Replies
1
Views
846
• Programming and Computer Science
Replies
97
Views
7K
• Programming and Computer Science
Replies
2
Views
2K
• Programming and Computer Science
Replies
5
Views
998
• Programming and Computer Science
Replies
10
Views
1K