I was wondering if I could write some code to find prime numbers up to a given integer, so took a morning off and wrote this in Python 3.5, which I perfected and made quicker after a couple of trials. I have managed to compute all prime numbers up to one million in 20 minutes, and from 0 to 10 million in 18 hours only using my laptop (check out “Prime Numbers up to TEN MILLION” or “Prime Numbers up to ONE MILLION“). I can’t even imagine how fast prime numbers would pop out if I could get hold of a supercomputer…
Before having a look at the code let’s remember what a prime number is (just in case, although if you’re reading this post you probably know already…). A prime number is simply a number which is only divisible by 1 and by itself (and no, 1 ISN’T a prime number). That’s it. Now let’s take a look at the code:
Basically, the code first asks the number up to which you want to find prime numbers and stores it as “n”. Then, before starting the computation, it directly prints the number 2 (it couldn’t be computed with this code) as it is the first prime. Now, before going into the iteration, notice the variable “prime_array” since it will be especially important later on the code. This variable is basically a list which will store every single prime number we find, and at the moment it only has the value 2 as a member.
We then have a for loop which will go through every single number from 3 to n-1. For each of these numbers it will make the variable “answer” be equal to 0 and start another for loop which goes through every single number from 0 to the “length” (number of members) of the list “prime_array” we were talking about before. For each of the current members of this list it divides the number we’re looking at by it, so we’re basically taking a number and dividing it by all previous prime numbers (we don’t have to divide it by all previous prime and non-prime numbers because prime numbers are basically the building blocks of all other numbers, so every non-prime number is a multiple of a prime number, and if a number isn’t divible by that prime number, it won’t be divisible by any mutiple of it either… So for example to see if 5 is a prime or not we don’t have to divide it by 2,3 and 4, but only by 2 and 3, since if it isn’t divisible by 2 it won’t be divisible by 4 either, as 4 is a multiple of 2. This makes the code much more effective at finding primes, computing all prime numbers up to 1 million over 20 times faster).
For each of these divisions we check to see if there’s a remainder (not divisible) or not (divisible). If there is a remainder nothing happens and the loop continues (so the number will then go on to being divided by the next prime number in the list…). However, if there isn’t a remainder, it means the number is divisible by that prime number, so it is a multiple of that prime number, meaning that it isn’t a prime (as we mentioned before, numbers are either prime numbers or multiples of those prime numbers). If these happens, then the variable “answer” goes on to equalling 1, and the second loop ends for that number, so we go on to the next one. If, however, by the end of the second loop “answer” is still equal to 0, that means the number hasn’t been divisible by any of the previous primes, meaning we’ve toppled over a new prime number! If this is so, the program prints out the prime number and adds this new prime to the “prime_array” list. The loop then moves on to the next number.
Here is the code I’ve written in Python 3.5. Feel free to use it and have fun!
print(“PRIME NUMBERS” + “\n”)
prime_array = [2]
n = int(input(“Enter the INTEGER up to which you want to search for primes” + “\n”))
print(“\n” + “Here are all of the primes up to ” + str(n) + “:” + “\n” + “\n” + “2” + “\n”)
for i in range(3,n):
answer = 0
for j in range(len(prime_array)):
if i%prime_array[j] == 0:
answer = 1
break
if answer == 0:
print(str(i) + “\n”)
prime_array.append(i)
CodeBubble 