1

I have this program to list prime numbers within a certain range. the problem is the larger the number the slower it becomes. how can i use numpy to imporve the speeds? if not numpy, is there any other way to speed up the calculations?

from datetime import date
import time
import numpy as np

today = date.today()

lower = int(input("Starting Number: "))
upper = int(input("Ending Number: "))

print("Prime numbers between",lower,"and",upper,"are:")
with open("primenumbers.txt","a") as file:
    file.write("\n")
    file.write("{}".format(today))
    file.write("\n")

start = time.time()

for num in range(lower,upper + 1):
   if num > 1:
       for i in range(2,num):
           if (num % i) == 0:
               break
       else:
         print(num)
         with open("primenumbers.txt","a") as file:
             file.write("\n")
             file.write("{}".format(num))
end = time.time()
print(end - start)

i want to process the data faster and please show some code.

Techy Savage
  • 15
  • 2
  • 8
  • "_the larger the number the slower it becomes_": yes, that's how prime numbers are. The greater the maximum number you have it check, the longer it will take. What's your question? – ifconfig Aug 26 '19 at 02:49
  • @ifconfig i understand that but how can i make the process faster. i see peaople use numpy to speed of the equations so how could i do that. – Techy Savage Aug 26 '19 at 03:03
  • 1
    `for i in range(2,num): if (num % i) == 0`... Oh, my... Please first optimize the values you are trying to compare. If the number is prime, then it will be odd and should have a divisor such that `divisor <= sqrt(num)` Including even numbers doubles the number of iterations you are performing, and searching all the way up to the number makes the number of iterations absolutely massive compared to searching up-to the square-root. Please go read up on Number Theory. Ideally, you should be caching in a sieve and using that to optimize your search. – Spencer D Aug 26 '19 at 03:03
  • @SpencerD im sorry i dont understand could you explain simpler please. im quite new to python and im not an adult so i dont have experience. – Techy Savage Aug 26 '19 at 03:05
  • 1
    Searching on '[numpy] prime' yielded this https://stackoverflow.com/q/49936222 among others. But benefits of using numpy for this are not clear. Python integers can be larger than numpy's int64. – hpaulj Aug 26 '19 at 03:32

2 Answers2

1

Sieve method is one of the efficient way to find the prime numbers. My answer is inspired from this Answer in SO. For 1 million I got a timeit of

16 ms ± 3.68 ms per loop (mean ± std. dev. of 7 runs, 100 loops each)

​ Numpy Implementation

def first_n_prime_numbres(n):    
    s = np.arange(3, n, 2)
    for m in range(3, int(n ** 0.5)+1, 2):         
        if s[(m-3)//2]: 
            s[(m*m-3)//2::m]=0
    return np.r_[2, s[s>0]]

first_n_prime_numbres(100)
min2bro
  • 4,509
  • 5
  • 29
  • 55
0

You are calculating the same numbers over and over again:

for num in range(lower,upper + 1):
   if num > 1:
       for i in range(2,num):

Instead you can save the results and check against them. Checkout dynamic programming.

drum
  • 5,416
  • 7
  • 57
  • 91
  • This doesn't explain _HOW_ to implement the fix. This, therefore, isn't an answer and should be posted as a comment. – ifconfig Aug 26 '19 at 02:51
  • so does anyone know the answer then? – Techy Savage Aug 26 '19 at 02:57
  • nvm i used a set and put the primes in it then listed it which speeded up the result but not by alot. although if someone knows how i can make it dynamic so it knows that would be great. – Techy Savage Aug 26 '19 at 03:28