Math SolutionsPythonSoftware Development

Using Python: Counting Prime Numbers

When children first hear of ‘prime’ numbers in elementary school, they are likely seen as just another abstract concept in mathematics.

However, like most of what we learned in elementary school, prime numbers have vast practical use in our world today, including in the world of computer programming and communications.

A prime number is a whole number greater than 1 whose only factors are 1 and itself. A factor is a whole numbers that can be divided evenly into another number. The first few prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23 and 29. Numbers that have more than two factors are called composite numbers.

Prime numbers are vitally important to communications. Most modern cryptography uses prime factors of large numbers. The large number that was used to encrypt a file can be publicly known and available, because the encryption works so only the prime factors of that large number can be used to decrypt it again. Though finding those factors is technically only a matter of time, it’s a matter of so much time that we say it cannot be done. A modern super-computer could chew on a 256-bit factorization problem for longer than the current age of the universe, and still not get the answer.

Primes are of the utmost importance to number theorists because they are the building blocks of whole numbers, and important to the world because their odd mathematical properties make them perfect for our current uses. It’s possible that new mathematical strategies or new hardware like quantum computers could lead to quicker prime factorization of large numbers, which would effectively break modern encryption. When researching prime numbers, mathematicians are always being both prosaic and practical.

Many programming exercises exist solely for the purpose of growing comfortable with using, sorting, collecting, and identifying prime numbers. Today’s post offers one such program, which requests from the user how many unique prime numbers they need and then returns them in an ordered list.

# A Python Program to find the first xxx prime numbers, printing them out
# as a list:
#
# DEFINITION:  A prime number (or a prime) is a natural number greater than 1 
# that has no positive divisors other than 1 and itself. ... For example, 5 is 
# prime because 1 and 5 are its only positive integer factors, whereas 6 is 
# composite because it has the divisors 2 and 3 in addition to 1 and 6.

# Initializing key variables and lists
prime = [2,3]
primeCount = 2
y = 4
done = False

# Gathering the number of primes needed from the user
print('')
limit = int(input('How many prime numbers would you like? '))

# Algorithm to calculate prime numbers the needed number of times
while done != True:
    differences = []
    for x in range(2,y-1):
        diff = abs((y/x) - (y//x))
        differences.append(diff)
    minDiff = min(differences)
    if minDiff > 0:
        prime.append(y)
        primeCount += 1
    if primeCount == limit:
        done = True
    y += 1

# Printing results
print('')            
print('The first',limit,'prime numbers are as follows')
print('')
print(prime)
print('')
print('List size = ',len(prime))

Leave a Reply