Noslog

其实对于质数的定义特别简单：只能被自己和 1 整出的数字就是质数。
定义如此简单，但是有很多性质却还是需要发掘的。

让我如此“好为人师”的原因是做了这样一道题目：

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

也就是说找出来 600851475143 的最大质因子

我开始的想法是列出来所有可能的素数，然后一个一个除下来，代码如下：

#!/usr/bin/env python
from math import *
def findPrimes(max):
    '''Finding primes'''
    N = max + 1
    prime = [0] * N
    list = []
    for i in range(2, N):
    	prime[i] = 1
    i = 2
    while (i * i) <= max:
    	if prime[i] == 1:
    		for j in range(2 * i, N):
    			if j % i == 0:
    				prime[j] = 0
    	i += 1
    for i in range(2, N):
    	if prime[i] == 1:
    		list.append(i)
    p = [0] * len(list)
    for i in range(len(p)):
    	p[i] = list[i]
    return p

number = input("Input your number:")
prime = findPrimes((int)(sqrt(number)))
for i in prime:
    if number % i == 0:
	print i ,

相信我，这个绝对可行！但是很 dirty
也就是效率很低，想法很笨><

后来在projecteuler上看到有人这么写的：

roots = [];
product = 1;
x = 2;
number = input("Number?");
y = number
while product != number:
    while (y % x == 0):
        roots.append(x)
        y /= x
        product *= roots[-1]
    x += 1
print roots

这样的方法执行出来和我那个相比简直就是瞬间完成阿！

大概的想法，我觉得就是，让输入的数字不断的变成质数～ 哈哈。。

学习了学习了。。

这样的解决方法也是充分利用了质数的性质阿！