It seems to me your second code example is wrong. You divide out only one prime factor and moving on testing for divisibility. If you enter, say: 8, it finds 2, divides it out, which gives 4, and will find 4 as largest prime that divides 8.
You have a lot of redundant tests, stepping b by one.
Consider this:
Write any positive number n as n = m + 6*q (q may be 0). Except for the prime numbers 2 and 3: If m is divisible by 2, then so is n (because 6 is divisible by 2). If m is divisible by 3, then so is n (again, because 6 is divisible by 3). The only chances for n to be prime is, if m is 1 or 5. Not all of those numbers are prime, but if it is prime, it will be 1 or 5 modulo 6.
That will add a few lines of code, to explicitly test for primes 2 and 3. But after that, it should speed up your algorithm. Just remember to divide out all powers of a prime before moving on. A single test could look like this: (Note that the following example does not test for n == 1)
n = int(input())
num = n
max=2max = 1
if n % 2 == 0:
max = 2
while n%2n % 2 == 0:
n //= 2
if n%3n % 3 == 0:
max = 3
while n%3n % 3 == 0:
n//= 3
b = 5
inc = 2
while n != 1:
if n%b==0n % b==0:
max=bmax = b
while n%bn % b == 0:
n //= b
b += inc
if inc == 2:
inc = 4
else:
inc = 2
It seems to me your second code example is wrong. You divide out only one prime factor and moving on testing for divisibility. If you enter, say: 8, it finds 2, divides it out, which gives 4, and will find 4 as largest prime that divides 8.
You have a lot of redundant tests, stepping b by one.
Consider this:
Write any positive number n as n = m + 6*q (q may be 0). Except for the prime numbers 2 and 3: If m is divisible by 2, then so is n (because 6 is divisible by 2). If m is divisible by 3, then so is n (again, because 6 is divisible by 3). The only chances for n to be prime is, if m is 1 or 5. Not all of those numbers are prime, but if it is prime, it will be 1 or 5 modulo 6.
That will add a few lines of code, to explicitly test for primes 2 and 3. But after that, it should speed up your algorithm. Just remember to divide out all powers of a prime before moving on. A single test could look like this: (Note that the following example does not test for n == 1)
n = int(input())
num = n
max=2
while n%2 == 0:
n //= 2
if n%3 == 0:
max = 3
while n%3 == 0:
n//= 3
b = 5
inc = 2
while n != 1:
if n%b==0:
max=b
while n%b == 0:
n //= b
b += inc
if inc == 2:
inc = 4
else:
inc = 2
It seems to me your second code example is wrong. You divide out only one prime factor and moving on testing for divisibility. If you enter, say: 8, it finds 2, divides it out, which gives 4, and will find 4 as largest prime that divides 8.
You have a lot of redundant tests, stepping b by one.
Consider this:
Write any positive number n as n = m + 6*q (q may be 0). Except for the prime numbers 2 and 3: If m is divisible by 2, then so is n (because 6 is divisible by 2). If m is divisible by 3, then so is n (again, because 6 is divisible by 3). The only chances for n to be prime is, if m is 1 or 5. Not all of those numbers are prime, but if it is prime, it will be 1 or 5 modulo 6.
That will add a few lines of code, to explicitly test for primes 2 and 3. But after that, it should speed up your algorithm. Just remember to divide out all powers of a prime before moving on. A single test could look like this:
n = int(input())
num = n
max = 1
if n % 2 == 0:
max = 2
while n % 2 == 0:
n //= 2
if n % 3 == 0:
max = 3
while n % 3 == 0:
n//= 3
b = 5
inc = 2
while n != 1:
if n % b==0:
max = b
while n % b == 0:
n //= b
b += inc
if inc == 2:
inc = 4
else:
inc = 2
It seems to me your second code example is wrong. You divide out only one prime factor and moving on testing for divisibility. If you enter, say: 8, it finds 2, divides it out, which gives 4, and will find 4 as largest prime that divides 8.
You have a lot of redundant tests, stepping b by one.
Consider this:
Write any positive number n as n = m + 6*q (q may be 0). Except for the prime numbers 2 and 3: If m is divisible by 2, then so is n (because 6 is divisible by 2). If m is divisible by 3, then so is n (again, because 6 is divisible by 3). The only chances for n to be prime is, if m is 1 or 5. Not all of those numbers are prime, but if it is prime, it will be 1 or 5 modulo 6.
That will add a few lines of code, to explicitly test for primes 2 and 3. But after that, it should speed up your algorithm. Just remember to divide out all powers of a prime before moving on. A single test could look like this: (Note that the following example does not test for n == 1)
n = int(input())
num = n
max=2
while n%2 == 0:
n //= 2
if n%3 == 0:
max = 3
while n%3 == 0:
n//= 3
b = 5
inc = 2
while n != 1:
if n%b==0:
max=b
while n%b == 0:
n //= b
b += inc
if inc == 2:
inc = 4
else:
inc = 2