CODEWITHSUNDEEP
pythonprimesmodulus
user3622114
user3622114

Reputation:

Python and the modulus operator with very large numbers

I apologize in advance if this is a duplicate question - my search for python and modulus ran up to 8 pages of questions and that combined with my relatively little coding experience made it somewhat difficult for me to check thoroughly to see if there was anything extremely similar out there.

While trying to solve a Project Euler question, I wrote a function for testing whether or not a number was a prime number:

import math
def isprime(n):
    if n % 1 != 0:
        return(False)
    else:
        for j in range(2, math.ceil(math.sqrt(n)) + 1):
            if n % j == 0:
                return(False)
            else:
                return(True)
        break

This works pretty well with small numbers, but with very large numbers that definitely aren't prime (e.g. I put in isprime(1012321312412431434334545555) and the function gives me a value of True). Why is this the case?

EDIT: as pointed out by roippi and confirmed by my further investigations, this function actually does not work for a lot of smaller odd composite numbers. I'm trying to figure out why that doesn't work for now.

Upvotes: 0

Views: 1684

Answers (2)

Kevin
Kevin

Reputation: 716

I believe your problem is that the return is in the wrong place. Your code currently only loops through the 2, and any odd number is obviously not divisible by 2. So, it goes into the if n%j==0, returns True, and since a return breaks out of the loop, stops going. So, any odd number will return True.

Instead, try:

def isprime(n):
    if n % 1 != 0:
        return True
    else:
        for j in range(2, math.ceil(math.sqrt(n))):
            if n % j != 0:
                return False
        return True

I think that works. EDIT: No, it actually doesn't. Here, I'll post a different prime checker:

def isprime(n):
    '''check if integer n is a prime'''
    n = abs(int(n))
    if n < 2:
        return False
    if n == 2: 
        return True    
    if not n & 1: 
        return False
    for x in range(3, int(n**0.5)+1, 2):
        if n % x == 0:
            return False
    return True

Upvotes: 1

wvdz
wvdz

Reputation: 16651

First of all, n % 1 == 0 will always return true for integers, because this tests if n is divisible by 1. So this is a bit of a nonsical test. If you want to check for odd/even numbers, use n % 2.

It does check for decimals, but in that case I think it's better to throw an error.

A better algorithm to test for prime is something like this:

def isPrime(n):
    if n < 2:
        return False
    if n < 4:
        return True
    for x in range(2,ceil(sqrt(n)) + 1):
        if (n % x == 0):
            return False
    return True

Upvotes: 1

Related Questions