SPOJ 2. Prime Generator

素數判斷算法，最簡單的為試除法，即若要判斷一個數n是否為素數，則判斷從2~sqrt(n)的數中的每個數m是否能被n整除，若能整除(n%m==0)則n明顯不是素數，否則即為素數。隻搜尋到sqrt(n)，可以通過下面的例子了解，假設n=100，

1*100=100
2*50=100
4*25=100
5*20=100
10*10=100
20*5=100
25*4=100
50*2=100
100*1=100
           

即100的約數有1,2,4,5,10,20,25,50,100共9個。但其實很明顯在從1找到10也就是sqrt(100)的前半部分的時候，如果100還有除了1以外的約數，就已經都找到了，sqrt(100)再到100之間的和前半部分是一樣的，隻是因子之間換了下位置而已。而如果某個數在2~sqrt(n)之間的前半部分沒有約數的話，那麼就說明在後半部分也不會有約數了。當然，這個方法是很慢的，是以代碼是TLE的，還有一些其他比較快的方法還沒仔細看，因為主要是想了解下python。

import math

t=input()
while t:
    l=raw_input()
    s=l.split(' ')
    m,n=int(s[0]),int(s[1])
    if m==1: m=2
    for num in xrange(m,n+1):
        f=1
        for i in xrange(2,int(math.sqrt(num))+1): #sqrt()傳回浮點數,xrange的參數需要整數
            if num%i==0:
                f=0
                break;
        if f: print str(num)
    print
    t-=1
           

1. 對于格式化輸入，比如題目中要求輸入1 10，好像隻能通過

l=raw_input()

s=l.split(' ')

m,n=int(s[0]),int(s[1])

來解決

2. range和xrange的卻别是range生成一個清單，如range(1,10000000)會生成一個10000000個元素的清單，很明顯這樣會占用很多記憶體，而xrange傳回的是一個數，和生成的範圍是無關的，其占用的記憶體大小是固定的。在時間上，xrange也會比range快。可以用下面的指令進行測試

$ python -m timeit 'for i in range(1000000):' ' pass'
10 loops, best of 3: 90.5 msec per loop
$ python -m timeit 'for i in xrange(1000000):' ' pass'
10 loops, best of 3: 51.1 msec per loop
           

但是看到說在python3.0以後就隻有range而沒有xrange了，range的功能類似于2.x中的xrange，沒有進行驗證。