54 lines
1.5 KiB
Python
54 lines
1.5 KiB
Python
#7. Algorithm for determining all Carmichael numbers less than a given bound.
|
|
|
|
import math
|
|
|
|
# Helper function to find all prime factors of a number
|
|
def prime_factors(n):
|
|
factors = set()
|
|
# Check for divisibility by 2
|
|
while n % 2 == 0:
|
|
factors.add(2)
|
|
n //= 2
|
|
# Check for odd factors from 3 upwards
|
|
for i in range(3, int(math.sqrt(n)) + 1, 2):
|
|
while n % i == 0:
|
|
factors.add(i)
|
|
n //= i
|
|
# If n is prime and greater than 2 then add it to the set
|
|
if n > 2:
|
|
factors.add(n)
|
|
return factors
|
|
|
|
# Function to check if a number is square-free (no repeated prime factors)
|
|
def is_square_free(n, prime_factors):
|
|
for p in prime_factors:
|
|
if n % (p * p) == 0:
|
|
return False
|
|
return True
|
|
|
|
# Function to check for Carmichael numbers
|
|
def is_carmichael(n):
|
|
prime_factors_of_n = prime_factors(n)
|
|
if(len(prime_factors_of_n)<2):
|
|
return False
|
|
if n < 3 or not is_square_free(n, prime_factors_of_n):
|
|
return False
|
|
for p in prime_factors_of_n:
|
|
if (n - 1) % (p - 1) != 0:
|
|
return False
|
|
return True
|
|
|
|
# Function to find all Carmichael numbers below a given bound
|
|
def carmichael_numbers_below(bound):
|
|
carmichaels = []
|
|
for n in range(3, bound):
|
|
if is_carmichael(n):
|
|
carmichaels.append(n)
|
|
return carmichaels
|
|
|
|
bound = 552722
|
|
carmichaels = carmichael_numbers_below(bound)
|
|
print(f"Carmichael numbers below {bound}:")
|
|
print(carmichaels)
|
|
|
|
#https://oeis.org/A002997 |