Optimized way of knowing number is prime or not?

Question


def print_prime_factors(number):
  # Start with two, which is the first prime
  factor = 2
  # Keep going until the factor is larger than the number
  while factor <= number:
    # Check if factor is a divisor of number
    if number % factor == 0:
      # If it is, print it and divide the original number
      print(factor)
      number = number / factor
    else:
      # If it's not, increment the factor by one
      factor += 1

      
  return "Done"

print_prime_factors(100)
# Should print 2,2,5,5
# DO NOT DELETE THIS COMMENT

I'm using this way for checking number is prime or not. Is there any other fast way?

See: https://en.wikipedia.org/wiki/Fermat%27s_little_theorem#Miller%E2%80%93Rabin_primality_test — Michael M., Dec 29 '22 at 17:22
The entire field of cryptography is based on how hard and slow it is to break a large number into its prime factors. Don't assume a shortcut exists. — Mark Ransom, Dec 29 '22 at 17:25
This [answer](https://stackoverflow.com/questions/2211990/how-to-implement-an-efficient-infinite-generator-of-prime-numbers-in-python/10733621#10733621) generates primes, which is a useful source of factors to try. (rather than using all factors with `factor+=1`) — quamrana, Dec 29 '22 at 17:26
@quamrana How is that useful? The candidates it lets you skip here were eliminated far more costly there. — Kelly Bundy, Dec 29 '22 at 17:28
@KellyBundy: Ok, I assumed it would be useful when `number` is very large. — quamrana, Dec 29 '22 at 17:40
@quamrana It's rather the opposite: that approach gets *slower* when `number` gets larger. Because more and more primes start sieving then. So the average cost per candidate increases. Whereas this approach here still only does one simple `%` per candidate. Although maybe it's not *far* more costly, just more... Looks like I overestimated the cost, it was indeed far more costly with similar but worse code I saw recently. — Kelly Bundy, Dec 29 '22 at 17:52
Ok, I think I see what you are saying. (I'm using `timeit` atm to get some data, but the code from the OP seems to be winning). — quamrana, Dec 29 '22 at 18:02

score -1 · Answer 1 · answered Dec 29 '22 at 20:34

You asked: Is there any other fast way?.

One way is to approx. halve the run time of your function by eliminating all the even factors (except 2):

def print_prime_factors_odd(number):
  # Start with two, which is the first prime
  factor = 2
  addend = 1
  # Keep going until the factor is larger than the number
  while factor <= number:
    # Check if factor is a divisor of number
    if number % factor == 0:
      # If it is, print it and divide the original number
      print(factor)
      number = number / factor
    else:
      # If it's not, increment the factor by the addend
      factor += addend
      addend = 2    # Once factor becomes 3, then use odd factors after that

      
  print("Done")

Optimized way of knowing number is prime or not?

1 Answers1