ASP 討論版

	昌爸工作坊論壇
\|─	質數倍數的判斷法


回覆	搜尋	返回	管理

作者	標題: 質數倍數的判斷法
藍天白雲	發表於: 2004/5/11 下午 03:07:53 有沒有前輩有很快速而且適用全部質數的方式目前就我知道的大概就只有去尾法但很麻煩有更快的嗎謝謝告知
Benjamin	回覆於: 2005/1/25 上午 12:18:41 適用全部數字的方法：找與10的N次方之差，將N位*差與前面相減或相加即可判別詳細內容，我以後在放上來請問如何判斷阿?例如:如何判斷有59的倍數
yani	回覆於: 2005/1/25 上午 01:44:16 適用於判斷任一數是否為質數的方法，目前絕對沒有﹗ 若有，那絕對是數學史上的大事﹗ 因為它克服了諸多整數論的猜測﹗ 也可以說﹕整數論這一數學分支，已被掌握、解決了﹗
J+W	回覆於: 2004/5/11 下午 03:21:35 適用全部質數的方式? 應該沒有吧
藍天白雲	回覆於: 2004/5/11 下午 03:24:04 那也就是說除了7.11.13之外其他的大概就直接除可能會比較快囉不管數字是什麼
johnHELEN	回覆於: 2004/5/11 下午 03:38:30 我也想知大大去尾法真的很麻煩學校只教去尾法
Carunty	回覆於: 2004/5/11 下午 03:42:17 In simple way ,there is two methods. square different method: if n+b^2=a^2 ，then n=(a+b)(a-b) square sum method: if N=a^2+b^2=c^2+d^2 then N=(ad+bc)(ad-bc)/(a+c)(a-c)
mmmmmmmm	回覆於: 2004/5/11 下午 03:43:55 你是要判斷一個數字是不是質數? 去年還是前年有個 PRIMES in P, 作者是 Agrawal, Kayal, Saxena 你在http://www.google.com應該可以找到, 這是目前知道的polynomial time判斷一個數字是不是質數的方法我是沒有看過這篇啦... 看懂了記得教一下 ^_^
饅頭	回覆於: 2004/5/11 下午 10:12:25 17的我知道將百位數2在與前兩位相減例：119要判別，將百位數12=2，19-2=17，所以原數為17的倍數適用全部數字的方法：找與10的N次方之差，將N位*差與前面相減或相加即可判別詳細內容，我以後在放上來
小昭	回覆於: 2025/3/16 上午 10:20:41 用饅頭的方法例子(17.1) 17判別法(1) 17*6=102=100-(-2) (以上為10^n士d型) 100a+b =102a-(2a-b) =17(6a)-(2a-b) 當2a-b為17的倍數, 則100a+b為17的倍數 (以上為饅頭做法的原因) 100=-2 (mod 17) 100^2=(-2)^2 (mod 17) 100^3=(-2)^3 (mod 17) ... 例123456788 =1(-2)^4+23(-2)^3+45(-2)^2 +67(-2)+88 (mod 17) =16-184+180-134+88 (mod 17) =-34=17(-2)=0 (mod 17) 所以123456788為17的倍數 (為11判別法的進化2.0版)
小昭	回覆於: 2025/3/16 上午 10:33:56 例子(17.2) 17判別法(2) 1759=1003=1000-(-3) 1000a+b =1003a-(3a-b) =17(59a)-(3a-b) 當3a-b為17的倍數, 則1000a+b為17的倍數 10^3=-3 (mod 17) 10^6=(-3)^2 (mod 17) 10^9=(-3)^3 (mod 17) ... 例:123456788 =123(-3)^2+456(-3)+788 (mod17) =1107-1368+788 (mod 17) =527=1731=0 (mod 17) 所以123456788為17的倍數
小昭	回覆於: 2025/3/16 上午 10:47:59 例子(59.1) 59判別法(1) 5917=1003=1000-(-3) 1000a+b =1003a-(3a-b) =59(17a)-(3a-b) 當3a-b為59的倍數, 則1000a+b為59的倍數 10^3=-3 (mod 59) 10^6=(-3)^2 (mod 59) 10^9=(-3)^3 (mod 59) ... 例123456792 =123(-3)^2+456(-3)+792 (mod59) =1107-1368+792 (mod 59) =531=599=0 (mod 59) 所以123456792為59的倍數