終於去屠豬館學習 and 搞定找大素數的python代碼

雖然不上課，但是在宿舍始終是不會認真學習的，畢竟開着會上微博，會看着wordpress後臺，最蛋疼還開着三國殺，這樣叫哥怎麼學習呢？索性逼自己去又熱人又多的屠豬館，中午吃完飯，就沒有回宿舍，去屠豬館，理清素數檢測那些東西，幸好去了屠豬館，不然這個東西又不知道拖到什麼時候了，囧！看完就回宿舍拿電腦到機房上《數值分析》的實驗課，我們組那個實驗報告被老師鄙視了，說這個不行，那個不行，說什麼這個要給出對比才行，不然人家怎麼知道你的做得快呀，唉，又得去搞蛋疼的matlab代碼，你妹的！哥估計要死了。

晚上也去了屠豬館，帶了電腦，不過上不了網，所以微博不了，殺不了，那就好好看python電子書和latex的電子書吧。所以python簡明教程看完了，算小會了python了，接下來編一些py文件，做下project euler或者codeforces去，不過最近要用python完成數論論文先，快點搞定，才有時間去搞其他，我是那種一段時間做不了那麼多事情的人，只能一件一件來，其他要落下就落下吧。latex現在看着，沒什麼太大的感覺，可能要出題考自己才行，不然看着看着就忘了。現在算小會python和latex，oh yeah！

搞定了數論找長度512位質數的代碼了，用python實現了，可以開始怎麼寫論文了，代碼實現參考《算法導論》，歡迎圍觀，也紀念我學python一週，剛剛也在BNUOJ用python做了A+B和一些水題。貼那個實現的代碼，這是初稿，稍後會加上代碼運行時間之類的，歡迎吐嘈，睡覺去，8點起來上物理課呢，不小心又三點。

代码在2011年5月12日23时52分25秒已作更新。

囧，发现那个函数Modular_exp写错了，已修改。

代码在2011年5月13日22时28分10秒已作更新。

#!/usr/bin/env python
 
# Time-stamp: <2011-05-13 16:07:03 Friday by roowe>
 
# @version 1.0
# @author roowe
 
import sys
import math
import random
import time
def Modular_exp(a,u,n):
    res = 1
    while u:
        if u & 1:
            res *= a
            res %= n
        a = a * a % n
        u >>= 1
    return res % n
def Witness(a,n):
    tt = (n - 1) & (1 - n)
    u = (n - 1) / tt
    t = int(math.log(tt, 2))
    x0 = Modular_exp(a,u,n)
    for i in range(1,t+1):
        x1 = x0 * x0 % n
        if x1 == 1 and x0 != 1 and x0 != n - 1:
            return True
        x0 = x1
    if x0 != 1:
        return True
    else:
        return False
start = time.clock()
n = random.randrange(2**512, 2**513);
if n&1:
    n += 1
for index in range(1, 1000, 2):
    m = n + index
    if Modular_exp(2,m-1,m) == 1:
        for i in range(1, 100):
            a = random.randrange(3, m)
            if Witness(a,m):
                break
        else:
            print index, m ,'is a prime'
elapsed = time.clock() - start
print "Time used",elapsed,"s"

順便貼下那結果，長這麼大還第一次大看這麼的素數（灰常大的可能是素數，99.9%）(结果已根据代码作相应的更新)

roowe@localhost ~/large_primes $ python test.py 
655 17094210769384804664141366453435892121842006013308787846576479093617896814850399181231975638041210507852385196997255839591090564411757408947645028035732457 is a prime
Time used 5.73 s
roowe@localhost ~/large_primes $ python test.py 
291 13893459929862877744465022942992821744940166038342844065518253288722201536565993547720414943494012226089711751888459400852925973509957082298858081930027037 is a prime
331 13893459929862877744465022942992821744940166038342844065518253288722201536565993547720414943494012226089711751888459400852925973509957082298858081930027077 is a prime
415 13893459929862877744465022942992821744940166038342844065518253288722201536565993547720414943494012226089711751888459400852925973509957082298858081930027161 is a prime
Time used 7.88 s
roowe@localhost ~/large_primes $

category - Life,python,流水帐　 tags - python, 大質數　 date - 2011 年 5 月 11 日　 comments - (16)

16 篇回應 (訪客:16 篇, 博主:0 篇)

Terry Chen ~

2011 年 5 月 11 日 10:35

现在努力做到能在宿舍学习，不过确实很容易走神。。。
想学LaTeX和R，等蛋疼的BEC过去我就比较有时间了，到时好好研究一下，不过也有很多书要看，或许假期再说咯。

回复
- Roowe ~
  
  2011 年 5 月 11 日 14:58
  
  書是看不完的～
  
  回复
  - Terry Chen ~
    
    2011 年 5 月 11 日 20:29
    
    我想在大三下学期之前看完国富论、资本论、通论和经济解释，压力很大啊！
    
    回复
    - Roowe ~
      
      2011 年 5 月 12 日 13:34
      
      Orz，那些只敢看看封面～
      
      回复
      - Terry Chen ~
        
        2011 年 5 月 12 日 16:38
        
        努力看过一遍再说吧。。。
zagfai ~

2011 年 5 月 11 日 12:35

剛在ZOJ 用python A了A+B … 看到你名字了.

回复
- Roowe ~
  
  2011 年 5 月 11 日 14:57
  
  那是在zoj那裏AC的唯一一道題目呀～～
  
  回复
zagfai ~

2011 年 5 月 11 日 12:36

還有… 我連上你的博客都要翻牆了.

回复
- Roowe ~
  
  2011 年 5 月 11 日 14:57
  
  我這裏暫時不用翻牆，據說牆的位置在發現變化～
  
  回复
kita ~

2011 年 5 月 12 日 14:20

python是不是tab比較重要的說，好像記憶中是這樣的，不需要{}這種符號的說

回复
- Roowe ~
  
  2011 年 5 月 12 日 15:42
  
  我的代码有出现{}吗？
  
  回复
  - kita ~
    
    2011 年 5 月 12 日 15:44
    
    沒有啊，沒有才說麼
    
    回复
Tanky Woo ~

2011 年 5 月 14 日 20:29

你咋啥都学？

回复
- Roowe ~
  
  2011 年 5 月 14 日 21:22
  
  酱油佬嘛
  
  回复
  - Tanky Woo ~
    
    2011 年 5 月 15 日 17:22
    
    毛啊，你是准备考研还是干嘛？
    
    回复
    - Roowe ~
      
      2011 年 5 月 15 日 20:34
      
      不清楚哦，我实在不愿意受这种填鸭教育
      
      回复