帐号 自动登录 找回密码 密码 欢迎注册
 搜索

# [讨论] 素性测试中的平方数判定问题

### 马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

x

(length = 2, number = 120, list = Any[1, 49])
(length = 6, number = 420, list = Any[1, 109, 121, 169, 289, 361])
(length = 6, number = 840, list = Any[1, 121, 169, 289, 361, 529])
(length = 30, number = 4620, list = Any[1, 169, 289, 361, 421, 529, 709, 841, 949, 961, 1369, 1549, 1621, 1681, 1849, 2209, 2269, 2641, 2689, 2809, 2941, 3061, 3301, 3469, 3481, 3529, 3721, 4141, 4321, 4489])
(length = 30, number = 9240, list = Any[1, 169, 289, 361, 529, 841, 961, 1369, 1681, 1849, 2209, 2641, 2689, 2809, 3481, 3529, 3721, 4321, 4489, 5041, 5329, 5569, 6169, 6241, 6889, 7561, 7681, 7921, 8089, 8761])
(length = 180, number = 60060, list = Any[1, 289, 361, 529, 841, 961, 1369, 1621, 1681, 1849, 2209, 2809, 2941, 3301, 3481, 3721, 4489, 5041, 5149, 5329, 5461, 5581, 5989, 6241, 6301, 6829, 6889, 7309, 7921, 8089, 8761, 8941, 9109, 9409, 9949, 10189, 10201, 10609, 10789, 10921, 11449, 11509, 11881, 12301, 12541, 12769, 13381, 13729, 13861, 14221, 14569, 14821, 15409, 16069, 16129, 16501, 16669, 17161, 17341,
18001, 18769, 18841, 18901, 19009, 19189, 19321, 20029, 20101, 20329, 20749, 21121, 21421, 21961, 22201, 22621, 22801, 23269, 23461, 23521, 24049, 24469, 24649, 24781, 25741, 25789, 26569, 26581, 27421, 27589, 27889, 28081, 28141, 28669, 28681, 29929, 30781, 31021, 31201, 31249, 32041, 32341, 32509, 32629, 32761, 33049, 33289, 34189, 34609, 35149, 35281, 36061, 36481, 36661, 37129, 37249, 37489, 37801, 37909, 38509, 38581, 38809, 39601, 39649, 39901, 40429, 40681, 41869, 41941, 42949, 43261, 43429, 44269, 44521, 44641, 45049, 45061, 45109, 45301, 46069, 46201, 46489, 46621, 47161, 48049, 48409, 48889, 49009, 49141, 49261, 49501, 49669, 49729, 49921, 50521, 50821, 50989, 51349, 51529, 51661, 51769, 52441, 53089, 53509, 53629, 53881, 54289, 54349, 54961, 55441, 55969, 56281, 56809, 56989, 57061, 57121, 58081, 58249, 58501, 58969, 59929])

楼主| 发表于 2019-10-8 09:05:32 | 显示全部楼层
 上面的数据里，有价值的是 (length = 2, number = 120, list = Any[1, 49]) 120=2^3*3*5 (length = 6, number = 840, list = Any[1, 121, 169, 289, 361, 529]) 840=2^3*3*5*7 最后一组，候选太多了，虽然数据比较好，待测试数除非很大，否则不建议选择 (length = 180, number = 60060, list = Any[1, 289, 361, 529, 841, 961, 1369, 1621, 1681, 1849, 2209, 2809, 2941, 3301, 3481, 3721, 4489, 5041, 5149, 5329, 5461, 5581, 5989, 6241, 6301, 6829, 6889, 7309, 7921, 8089, 8761, 8941, 9109, 9409, 9949, 10189, 10201, 10609, 10789, 10921, 11449, 11509, 11881, 12301, 12541, 12769, 13381, 13729, 13861, 14221, 14569, 14821, 15409, 16069, 16129, 16501, 16669, 17161, 17341, 18001, 18769, 18841, 18901, 19009, 19189, 19321, 20029, 20101, 20329, 20749, 21121, 21421, 21961, 22201, 22621, 22801, 23269, 23461, 23521, 24049, 24469, 24649, 24781, 25741, 25789, 26569, 26581, 27421, 27589, 27889, 28081, 28141, 28669, 28681, 29929, 30781, 31021, 31201, 31249, 32041, 32341, 32509, 32629, 32761, 33049, 33289, 34189, 34609, 35149, 35281, 36061, 36481, 36661, 37129, 37249, 37489, 37801, 37909, 38509, 38581, 38809, 39601, 39649, 39901, 40429, 40681, 41869, 41941, 42949, 43261, 43429, 44269, 44521, 44641, 45049, 45061, 45109, 45301, 46069, 46201, 46489, 46621, 47161, 48049, 48409, 48889, 49009, 49141, 49261, 49501, 49669, 49729, 49921, 50521, 50821, 50989, 51349, 51529, 51661, 51769, 52441, 53089, 53509, 53629, 53881, 54289, 54349, 54961, 55441, 55969, 56281, 56809, 56989, 57061, 57121, 58081, 58249, 58501, 58969, 59929]) 60060=2^2*3*5*7*11*13 这组可以用 (length = 30, number = 9240, list = Any[1, 169, 289, 361, 529, 841, 961, 1369, 1681, 1849, 2209, 2641, 2689, 2809, 3481, 3529, 3721, 4321, 4489, 5041, 5329, 5569, 6169, 6241, 6889, 7561, 7681, 7921, 8089, 8761])  9240=2^3*3*5*7*11 代替，180/60060=0.002997，30/9240=0.0003247，差距很小

楼主| 发表于 2019-10-8 09:16:19 | 显示全部楼层
 global cnt = (length = 65536, number = 65537, list = []) println("Begin") for m in range(120, step = 2, stop = 65536)     global s = []     for i in range(1, stop = m-1)         if gcd(i, m) == 1             t = i * i % m             push!(s, t)         end     end     sort!(s)     unique!(s)     if cnt.length//cnt.number > length(s)//m         global cnt = (length = length(s), number = m, list = s)         println(cnt)     end end println("End")          复制代码

 求平方根是很快的 https://gmplib.org/manual/Integer-Roots.html 函数mpz_sqrt 得到平方根以后，在自相乘，再判断结果是否等于原整数即可

楼主| 发表于 2019-10-8 10:16:30 | 显示全部楼层
 function isSquareOrDivBy2357(n)     if gcd(n, 840) != 1         return true     end     t = n % 840     if t in [1, 121, 169, 289, 361, 529]         sq = isqrt(n)         return sq * sq == n     else         return false     end end for i in range(1, stop = 65535)     t = i * i     if !isSquareOrDivBy2357(t)         print("error at \$i * \$i = \$t")     end end t = big(10)^67 - 1 println("\$t: ", isSquareOrDivBy2357(t)) t = t * t println("\$t: ", isSquareOrDivBy2357(t)) 复制代码

楼主| 发表于 2019-10-8 10:42:10 | 显示全部楼层
 mathe 发表于 2019-10-8 10:05 求平方根是很快的 https://gmplib.org/manual/Integer-Roots.html 函数mpz_sqrt 我知道，但是我想先筛选掉绝大部分不是平方的数

楼主| 发表于 2019-10-8 10:51:07 | 显示全部楼层
 function isSquareOrDivBy2357(n)     if gcd(n, 840) != 1         return true     end     t = n % 840     if t in [1, 121, 169, 289, 361, 529]         sq = isqrt(n)         return sq * sq == n     else         return false     end end function isSquare1(n)     sq = isqrt(n)     return sq * sq == n end @time for i in range(1, stop = 65535)     t = i * i     if !isSquareOrDivBy2357(t)         print("error at \$i * \$i = \$t")     end end @time for i in range(1, stop = 65535)     t = i * i     if !isSquare1(t)         print("error at \$i * \$i = \$t")     end end t = t * t @time println("\$t: ", isSquareOrDivBy2357(t)) @time println("\$t: ", isSquare1(t)) 复制代码 好吧，结果果然不如直接开平方~ 0.004386 seconds (14.98 k allocations: 1.828 MiB)   0.000710 seconds 9999999999999999999999999999999999999999999999999999999999999999996000000000000000000000000000000000000000000000000000000000000000000599999999999999999999999999999999999999999999999999999999999999999960000000000000000000000000000000000000000000000000000000000000000001: true   0.072349 seconds (197.96 k allocations: 10.581 MiB, 15.72% gc time) 9999999999999999999999999999999999999999999999999999999999999999996000000000000000000000000000000000000000000000000000000000000000000599999999999999999999999999999999999999999999999999999999999999999960000000000000000000000000000000000000000000000000000000000000000001: true   0.018368 seconds (2.21 k allocations: 106.926 KiB)

### 点评

 借题，问一下，可有此类算法：可快速判定一个大整数，有/无 含非 1 的平方因子？

 验证n是完全平方数 sqrt(n)求一下看看是不是整数，不就出结果了吗？

 gxqcn 发表于 2019-10-8 17:12 借题，问一下，可有此类算法：可快速判定一个大整数，有/无 含非 1 的平方因子？ 3年前我问过，也再问一下。 https://bbs.emath.ac.cn/thread-9242-1-1.html

 您需要登录后才可以回帖 登录 | 欢迎注册 本版积分规则 回帖后跳转到最后一页

GMT+8, 2020-2-27 12:43 , Processed in 0.166100 second(s), 20 queries .