0

I've written an algorithm that checks if a number is prime or not. it works just fine but when the integer value gets close to 1 million it begins to slow and when it's exactly 1 million it gets stuck trying to determine if it's prime or not.

here's is what i've tried

def isPrime(n):

    c = []
    for i in range(1, n+1):
        if i % i == 0 and n % i == 0:
            c.append(i)
    if len(c) > 2 or len(c) == 1:
        return(0)
    return(1)

https://pastebin.com/embed_js/CKC4sGFy

def factors(n):

    for i in range(1, n+1):
        if n % i == 0:
            if isPrime(i):
                print(i)

here i wrote another algorithm for prime factors calling on the prime checker

https://pastebin.com/embed_js/VLUCSK3s

coda99
  • 1
  • 1
  • 2
    Hm, `if i % i == 0` doesn't make any sense, because that condition is `true` per defintion ... – derpirscher Dec 16 '22 at 14:36
  • 2
    For once you can only go to the root, more in herehttps://stackoverflow.com/questions/46841968/fastest-way-of-testing-if-a-number-is-prime – Dani Mesejo Dec 16 '22 at 14:36
  • You can stop when you found the first didvisor != n. (except 1) – MrSmith42 Dec 16 '22 at 14:37
  • you could only try to divide by to and than only check odd numbers ;-) – MrSmith42 Dec 16 '22 at 14:39
  • @MrSmith42 only if `i > 1` and `n != 2` – derpirscher Dec 16 '22 at 14:39
  • Ad mentioned, the `i % i == 0` check is absurd. It's always true. This strongly suggests that you don't really understand the algorithm that you're using, so a good starting point would be to understand the math solidly before attempting to translate it into code. That said, your look is running way too many iterations. The largest factor you need to check is the square root of `n`. If it has any larger factor, then it must also have a corresponding smaller factor that you will have checked. – Tom Karzes Dec 16 '22 at 14:39
  • 1
    And of course, the only even factor you need to check is `2`. After that, you should skip the even factors and just check `3`, `5`, `7`, etc. – Tom Karzes Dec 16 '22 at 14:40
  • It will also often be a lot faster if you stop as soon as you find a divisor, rather than seeing at the end how many there were. – match Dec 16 '22 at 14:41
  • You can also avoid divisors of 5. After the 10 first numbers, you only need to check numbers ending in `1`,`3`,`7` or `9`. – DRTorresRuiz Dec 16 '22 at 14:42
  • thank you guys, @TomKarzes i'd definitely make the adjustments, thanks for pointing out checking for the largest factor of `n` i didn't consider that – coda99 Dec 16 '22 at 14:49

0 Answers0