Re: [問題] 判斷質數等不到所有數都除過就判定了?

看板C_and_CPP (C/C++)作者 (愛吃蘋果的孩子)時間16年前 (2009/08/30 10:42), 編輯推噓1(218)
留言11則, 4人參與, 最新討論串2/3 (看更多)
※ 引述《Euler (http://0rz.tw/bd3Jx )》之銘言: : http://nopaste.info/50b7b07400.html : 這是我寫的判斷質數 : 但是寫完之後我才發現一個問題 : 我想不到要如何一個數N : 從1~N除完才判斷它是質數 可以用i/根號i -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 122.126.144.104

08/30 12:28, , 1F
可以用推文...........
08/30 12:28, 1F

08/30 12:30, , 2F
跑暴力算質數別用if(sqr(n)>i)
08/30 12:30, 2F

08/30 12:31, , 3F
應該要用 if(n>i*i) 這樣效率會比較好
08/30 12:31, 3F

08/30 13:06, , 4F
>=
08/30 13:06, 4F

08/30 17:04, , 5F
sqrt(n)可以先算出來放到某變數去, 這樣還比i*i慢嗎?_?
08/30 17:04, 5F

08/30 17:07, , 6F
問題在浮點數比較應該會比較耗時吧XD
08/30 17:07, 6F

08/30 17:10, , 7F
還有include math.h 程式會變肥XD
08/30 17:10, 7F

08/30 17:10, , 8F
sqrt(n)出來的結果可以直接捨棄小數存進整數變數, 這樣
08/30 17:10, 8F

08/30 17:11, , 9F
迴圈就只是整數比較, 我只是比較好奇這個只算一次的東西
08/30 17:11, 9F

08/30 17:11, , 10F
跟迴圈一直算i*i比起來, 誰的計算overhead比較大:)
08/30 17:11, 10F

08/30 19:16, , 11F
低能..
08/30 19:16, 11F
文章代碼(AID): #1AcURwpC (C_and_CPP)
文章代碼(AID): #1AcURwpC (C_and_CPP)