(Python) 求解質數問題

取自slideshare

以下是程式內容:

# -*- coding: utf-8 -*-
number = int(input('give me a number: ')) #輸入一個數字來判別
half = number // 2      #定義half為number=輸入數字/2
 
#以下把num連續2到half+1之間整數做驗證能否整除number, 若能則該數不是質數

for num in range(2, half + 1):    
    if (number % num) == 0:     
        print(number, 'not a prime and can by divide by', num)
        break
else:
    print(number, 'is a prime')

不過上面質數求解的方式能找出最小除數, 下方有一篇程式列出所有可以整除的除數(從小到大). 數學問題(ex. 被除數為600851475143)

import math
def is_prime_number(x):
   for i in range(int(math.sqrt(x)), 2, -1):
      if x % i == 0:
        return False
   return True

def next_prime_number(number):
    #Returns the next prime number.
    if number % 2 == 0 and number != 2:
        number += 1
    while not is_prime_number(number):
        number += 2
    return number

num = 600851475143
i = 2
while (i < long(math.sqrt(num) / 2)):
    if num % i == 0:
       largest = i
       print largest
    i = next_prime_number(i + 1)

延伸討論: (蠻有趣的說)

1. (Stackoverflow) Python "OverflowError"
2. 葉難  Project Euler與Python