在Python中如何写一个大整数的快速乘法程序 - 编程论坛

#2

ysr28572022-12-14 17:37

判断素数的程序

Python代码：

from math import sqrtdef is_prime(n): if n == 1: return False for i in range(2, int(sqrt(n))+1): if n % i == 0: return False return True

这个程序对吗？

#3

mrexcel2022-12-16 16:01

以下是引用ysr2857在2022-12-14 17:37:10的发言：

判断素数的程序

Python代码：

from math import sqrtdef is_prime(n): if n == 1: return False for i in range(2, int(sqrt(n))+1): if n % i == 0: return False return True

这个程序对吗？

没有测试，感觉至少2会出问题。return False之后加一行break

可以直接引用sympy库 from sympy import isprime

#4

mrexcel2022-12-16 16:05

几十万位的两个数的乘法得3个小时？

什么算法也快不到哪里去，几千亿位的结果存储是个大问题，有什么意义呢？

#5

mrexcel2022-12-16 23:29

以下是引用ysr2857在2022-12-14 17:37:10的发言：

判断素数的程序

Python代码：

from math import sqrtdef is_prime(n): if n == 1: return False for i in range(2, int(sqrt(n))+1): if n % i == 0: return False return True

这个程序对吗？

你的代码测试通过，可以不引用math库。

程序代码：

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5+1)):
        if n % i == 0:
            return False
    return True

print([n for n in range(1,100) if is_prime(n)])

或者通过忽略偶数，减少循环进行优化，如：

程序代码：

def is_prime(n):
    if n == 1 or (n%2==0 and n>2):
        return False
    for i in range(3,int(n**0.5+1),2):
        if n % i == 0:
            return False
    return True

print([n for n in range(1,100) if is_prime(n)])

#6

ysr28572022-12-17 04:52

回复 5楼 mrexcel

谢谢老师指导！对于Python语言我是菜鸟一点儿不懂，我仅仅会一点VB语句。

非常感谢！

判断大整数是否素数，我用欧拉原理（欧拉定理和推论）编程的VB代码，经过优化后可以在3秒内判断一个100多位的大素数。如果用Python再快点儿就可以用来搜索巨大的孪生素数，甚至可以破解世界纪录。

#7

ysr28572022-12-17 04:59

任何数学规律都是有价值的可以用于实际的，素数的一些规律（差定理和和定理就是哥德巴赫猜想等），起码有助于我们快速找到我们需要的巨大的素数或孪生素数，当然还要结合其他技术知识如计算大整数的快速程序，下面这对大孪生素数就是应用前面的规律找到的：

1000002100内有1组3生素数:
1000001329,9173994463960286046443283581208347763186259956673124494950355357547691504353939232280074212440503746219891,9173994463960286046443283581208347763186259956673124494950355357547691504353939232280074212440503746219893,4n+2=9173994463960286046443283581208347763186259956673124494950355357547691504353939232280074212440502746218562（含有一对106位的孪生素数）——
用时9692.083秒

#8

ysr28572022-12-17 05:30

20000与21000之间的素数打头有1组差为1606938044258990275541962092341162602522202993782792835301376和2的整数加孪生素数对: (用时682.9688秒）
//20593/1606938044258990275541962092341162602522202993782792835321969/1606938044258990275541962092341162602522202993782792835321971

这是一对61位的孪生素数

#9

mrexcel2022-12-17 14:09

以下是引用ysr2857在2022-6-27 10:53:45的发言：

如下为vb代码：
Public Function MbC(D1 As String, D2 As String) As String
Dim j1&, j2&, e&, d&, e1&

   ' 按列法计算C=A*B
m = Trim(D1): n = Trim(D2)
x = Len(m) \ 4: Y = Len(n) \ 4
m = String(4 * x + 4 - Len(m), "0") & m
n = String(4 * Y + 4 - Len(n), "0") & n
x = x + 1: Y = Y + 1
Dim A(), B()
ReDim A(1 To x): ReDim B(1 To Y)
For i1 = 1 To x
A(i1) = Val(Mid(m, i1 * 4 - 3, 4))
Next
For i2 = 1 To Y
B(i2) = Val(Mid(n, i2 * 4 - 3, 4))
Next
ma = x: mb = Y
    MC = ma + mb
    ReDim c(MC)
    e1 = 0
    j1 = ma: j2 = ma
    For I = MC To 2 Step -1
        If I <= ma Then j2 = I - 1
        e = e1: e1 = 0
        For J = j1 To j2
            e = e + A(J) * B(I - J)
            If e > 2040000000 Then '减少进位次数
                e = e - 2040000000
                e1 = e1 + 204000
            End If
        Next J

        If j1 > 1 Then j1 = j1 - 1
base = 10000
        d = e \ base
        c(I) = e - d * base
        If Len(c(I)) < 4 Then
        c(I) = String(4 - Len(c(I)), "0") & c(I)
        Else
        c(I) = c(I)
        End If
jc = c(I) & jc
        e1 = e1 + d
    Next I
    jc = d & jc
   MbC = qqdl(Trim(jc))
End Function

这个程序算几十万位的两个数的乘法得3个小时，太慢了！

MbC = qqdl(Trim(jc)),qqdl是个什么函数？

#10

mrexcel2022-12-17 14:11

Python支持大数直接运算，做数论的东西，还是建议选择Python 或 Mathematica 或者 Pari

#11

mrexcel2022-12-17 14:14

from sympy import nextprime
n=1606938044258990275541962092341162602522202993782792835321969
p=nextprime(n)
print(p,p-n)

1606938044258990275541962092341162602522202993782792835321971 2

#12

mrexcel2022-12-17 14:23

from sympy import nextprime
n=9173994463960286046443283581208347763186259956673124494950355357547691504353939232280074212440503746219891
for k in range(1,11):
print(k,nextprime(n**k)-n**k)

1 2
2 22
3 110
4 328
5 878
6 1060
7 740
8 7042
9 11442
10 60

#13

ysr28572022-12-17 23:23

回复 9楼 mrexcel

是去前导0的程序，谢谢您的指导！

#14

ysr28572022-12-17 23:25

回复 10楼 mrexcel

谢谢您！我对Python一点都不懂，欢迎沟通和指导！需要好好学习啊！

#15

ysr28572022-12-17 23:26

回复 12楼 mrexcel

这个数据是啥意思？我没有看明白呀，咋回事啊我前面那个数不对吗？

#16

mrexcel2022-12-17 23:31

以下是引用ysr2857在2022-12-17 23:26:51的发言：

这个数据是啥意思？我没有看明白呀，咋回事啊我前面那个数不对吗？

12楼代码返回最小的素数p=9173994463960286046443283581208347763186259956673124494950355357547691504353939232280074212440503746219891^n+k 对应的n,k

我的意思是，PYTHON计算大数字比VB优势太多

#17

ysr28572022-12-19 22:39

回复 16楼 mrexcel

啊谢谢！Python处理大数确实快很多，我需要好好学习啊！谢谢您指导！

#18

陆戴02142022-12-21 12:38

math语句非常实用

#19

ysr28572022-12-21 13:49

回复 18楼陆戴0214

谢谢关注和指导！math语言我也不会啊，需要好好学习啊！向各位老师学习！

#20

ysr28572022-12-22 10:57

回复 16楼 mrexcel

有1060位，用时3.90625E-03秒4222646610334809789950335202679792592987460667289706764761891712126761395308224803518878544060045025191466725449543696425560304974974952598736645076105201823075658763243948227081708664288023222547022874171434101741944770826063821105909123068018240610389271568701906932157614335016097892642327046878595303542698205711612330205600894174330798317683238958933351446729305885468873287056895575775126972188310087972984285552559393329384947436901201696808781726796005028176639462142103355668599577925241181832100925924318974820149639134446341576521013825390518460550851527460768836792495721837206727351057520505722493681890678022069950609340097236873635215659531727368411461874967165445199808800434869905137885350489632031967978006388967138069090072994818927919052502945327320943981967979152918588228901811530957113748812783690702497671735050892424595361881506282786097765698728230478672322457675919312203482858122649371100598014407183889507717060663492200973908332369369057714409031855132234704279376263757534918490941449540519365412647673217856643876810404615923461.

这个是素数吗？我的程序太慢，要判断这个得好长时间呢

#21

ysr28572022-12-22 11:04

该数分解网站无法分解，该数就是9173994463960286046443283581208347763186259956673124494950355357547691504353939232280074212440503746219891的10次方加60.

#22

mrexcel2022-12-22 16:13

以下是引用ysr2857在2022-12-22 11:04:56的发言：

该数分解网站无法分解，该数就是9173994463960286046443283581208347763186259956673124494950355357547691504353939232280074212440503746219891的10次方加60.

4222 646610 334809 789950 335202 679792 592987 460667 289706 764761 891712 126761 395308 224803 518878 544060 045025 191466 725449 543696 425560 304974 974952 598736 645076 105201 823075 658763 243948 227081 708664 288023 222547 022874 171434 101741 944770 826063 821105 909123 068018 240610 389271 568701 906932 157614 335016 097892 642327 046878 595303 542698 205711 612330 205600 894174 330798 317683 238958 933351 446729 305885 468873 287056 895575 775126 972188 310087 972984 285552 559393 329384 947436 901201 696808 781726 796005 028176 639462 142103 355668 599577 925241 181832 100925 924318 974820 149639 134446 341576 521013 825390 518460 550851 527460 768836 792495 721837 206727 351057 520505 722493 681890 678022 069950 609340 097236 873635 215659 531727 368411 461874 967165 445199 808800 434869 905137 885350 489632 031967 978006 388967 138069 090072 994818 927919 052502 945327 320943 981967 979152 918588 228901 811530 957113 748812 783690 702497 671735 050892 424595 361881 506282 786097 765698 728230 478672 322457 675919 312203 482858 122649 371100 598014 407183 889507 717060 663492 200973 908332 369369 057714 409031 855132 234704 279376 263757 534918 490941 449540 519365 412647 673217 856643 876810 404615 923461 (1060 digits) is prime

#23

ysr28572022-12-22 21:41

回复 22楼 mrexcel

谢谢！您的程序速度就是快！我还需要好好学习！向各位老师学习！

#24

风卷浪起2022-12-30 17:16

#25

sssooosss2022-12-31 20:29

新年快乐

#26

ysr28572023-01-01 22:13

各位老师和朋友新年快乐！