(정수론/파이썬) 소수 이후 합성수가 연이어 나올 때

# 소수 492,113부터는 합성수가 113개 연달아 나온다.
# 소수 다음에 합성수가 일정 횟수 이상 연이어 나온다면 그 앞뒤의 소수와 합성수 출현 횟수를 출력

# 해당 숫자가 소수인지 판정하는 함수
def isPrime(num):
  root_val = round(num ** 0.5) # 제곱근 값을 구한다
  for i in range(2, root_val+1): # 제곱근값+1 까지만 약수를 조사해도 충분하다
    if num % i == 0:  # 중간에 나눠지면 소수가 아니다
      return False
  return True   # 끝까지 나눠지지 않을 경우, 소수로 판정하고 리턴한다.


MAX_NUM = 1000000  # 까지 검사한다
LEAST = 90  # 합성수가 이 개수만큼 연이어 나온다면
c_count = 0   # 연이은 합성수 출현 횟수 초기화
lst = []      # 연이은 합성수 출현 횟수와 그 시작 소수 기록

for i in range(2, MAX_NUM):
  if isPrime(i) != True:  # 합성수라면
    c_count += 1
  else:      # 소수라면 
    if c_count >= LEAST:
      print(f"합성수 {c_count} 개: 소수 {prev_prime} ~ 소수 {i}")
      lst.append((prev_prime, c_count))
    prev_prime = i
    c_count = 0

# 연이은 합성수가 제일 많은 구간 찾기
max_count = 0    # 연이은 합성수 출현 횟수 초기화
prime_start = 2  # 첫 소수로 초기화

for start, count in lst:
  if max_count < count:
    max_count = count
    prime_start = start

print()
print(f"최대: 소수 {prime_start}에서부터 합성수 연이은 출현 횟수 : {max_count} 회")

결과:

합성수 95 개: 소수 360653 ~ 소수 360749
합성수 111 개: 소수 370261 ~ 소수 370373
합성수 99 개: 소수 396733 ~ 소수 396833
합성수 113 개: 소수 492113 ~ 소수 492227
합성수 97 개: 소수 604073 ~ 소수 604171
합성수 99 개: 소수 838249 ~ 소수 838349
합성수 95 개: 소수 860143 ~ 소수 860239
합성수 91 개: 소수 927869 ~ 소수 927961

최대: 소수 492113에서부터 합성수 연이은 출현 횟수 : 113 회