- 主题:如何加快运算速度？请指教
我有1029个不相同的素数，然后 要从中取出若干个素数（无重复），把它们乘起来构成一个大整数 N, 要求N的每一个素因子 p 都满足条件
p-1 整除 N-1，且 p+1 整除 N+1
（只要计算奇数个素因子的乘积，再验算就行了）
我写python代码，初步验算了一下 取三个素数，算乘积，再验算的情况，有181，062，154种（1029中取3的组合数）。可是太慢了，10分钟还没计算完。
后面还有取5个，7个，9个，。。。。。。1025个素数算乘积的情况。这何时是个头啊？大佬，有加速的方法吗？
※ 修改:·feng321 于 Mar 16 12:16:24 2023 修改本文·[FROM: 120.242.253.*]
※ 来源:·水木社区
http://www.mysmth.net·[FROM: 120.242.253.*]
修改:feng321 FROM 120.242.253.*
FROM 120.242.253.*
半个小时，跑完了3个素数相乘的情况。如果用gpu，有加速的可能吗？
【 在 feng321 的大作中提到: 】
: 我有1029个不相同的素数，然后 要从中取出若干个素数（无重复），把它们乘起来构成一个大整数 N, 要求N的每一个素因子 p 都满足条件
: p-1 整除 N-1，且 p+1 整除 N+1
: （只要计算奇数个素因子的乘积，再验算就行了）
: ...................
--
FROM 120.242.253.*
q你的这个素数有多少位？是固定的集合还是变的？ 大数乘法是怎么算的？感觉光算这个乘积都有优化空间
另外是不是可以先做一些简单的验证 乘积pai先保留10000以下的部分
p-1 p+1 有很多数字是可以根据后面的几位验证的
比如 p-1 or p+1 %4==0 需要判断 pai后两位%4==0 就可以了
另外p-1 p+1都可以因数分解 先把1029*2个数因数分解 按小的粒度判断 一下
数学上有没有什么理论和方法能分解这个问题呢
看了下你这素数范围很大数量又不少 很难啊
--
修改:ip5 FROM 115.183.224.*
FROM 101.41.103.*
谢谢，1029个素数，是固定的集合。但是p是不固定的。比如5个素数的乘积是N，那么p有可能取这5个当中的一个。
【 在 ip5 的大作中提到: 】
: 你的这个素数有多少位？是固定的集合还是变的？ 大数乘法是怎么算的？感觉光算这个乘积都有优化空间
: 另外是不是可以先做一些简单的验证 乘积pai先保留10000以下的部分
: p-1 p+1 有很多数字是可以根据后面的几位验证的
: ...................
--
FROM 120.242.253.*
这个数学上有解吗
p是n的因子
p-1是n-1的因子
每一个都满足，每一个因子都减1之后乘积也只减1，有可能吗
【 在 feng321 的大作中提到: 】
: 我有1029个不相同的素数，然后 要从中取出若干个素数（无重复），把它们乘起来构成一个大整数 N, 要求N的每一个素因子 p 都满足条件
: p-1 整除 N-1，且 p+1 整除 N+1
: （只要计算奇数个素因子的乘积，再验算就行了）
: ...................
--
FROM 121.33.161.*
1087*1087*1087 = 1，284，365，503
1，284，365，503 / 1087 = 1,181,569
1，284，365，502 / 1086 = 1,182,657
1，284，365，504 /10 88 == 1,180,483
1087 也是我这个素数表里面的一个素数。只是三个重复了，不合要求
【 在 iMx 的大作中提到: 】
: 这个数学上有解吗
: p是n的因子
: p-1是n-1的因子
: ...................
--
FROM 120.242.253.*
如果不考虑算法，单纯的加速可以考虑编译为C代码
又仔细看了下、优化算法吧、上面的方式对性能的影响几乎没有。
【 在 feng321 的大作中提到: 】
:
: 我有1029个不相同的素数，然后 要从中取出若干个素数（无重复），把它们乘起来构成一个大整数 N, 要求N的每一个素因子 p 都满足条件
:
: p-1 整除 N-1，且 p+1 整除 N+1
: （只要计算奇数个素因子的乘积，再验算就行了）
#发自zSMTH@PCT-AL10
--
※ 来源:水木社区 [1.68.108.*(山西太原)]
#修改自zSMTH@PCT-AL10
※ 修改:·CduVgg 于 Mar 4 16:56:07 2023 修改本文·[FROM: 1.68.108.*]
※ 来源:·水木社区
http://www.mysmth.net·[FROM: 1.68.108.*]
修改:CduVgg FROM 1.68.108.*
FROM 1.68.108.*
p-1 与n-1 可以填其他因素
p+1 与n+1,没得填了吧
【 在 feng321 的大作中提到: 】
: 1087*1087*1087 = 1，284，365，503
: 1，284，365，503 / 1087 = 1,181,569
: 1，284，365，502 / 1086 = 1,182,657
: ...................
--
FROM 121.33.161.*
你这什么意思？不懂啊。n=p1*p2*p3*p4*p5, 大佬，有快速计算两个大数乘积、取模的库吗？numpy能计算两个大数的乘积吗？怎么计算？
【 在 iMx 的大作中提到: 】
: p-1 与n-1 可以填其他因素
: p+1 与n+1,没得填了吧
:
--
FROM 120.242.253.*
你另外帖子里面的代码：
可以改成下面这样，能少算几次：
flag = False
#五个素数的乘积-1
for il in range(0,1025):
for i2 in range(i1+1,1026):
m2 = data2[i1][0] * data2[i2][0]
for i3 in range(i2+1,1027):
m3 = m2 * data2[i3][0]
for i4 in range(i3+1,1028):
m4 = m3 * data2[i4][0]
for i5 in range(i4+1,1029) :
五个素数的乘积 = m4 * data2[i5][0]#print(五个素数的乘积)
计算的库可以试试 gmpy2。
【 在 feng321 的大作中提到: 】
: 我有1029个不相同的素数，然后 要从中取出若干个素数（无重复），把它们乘起来构成一个大整数 N, 要求N的每一个素因子 p 都满足条件
: p-1 整除 N-1，且 p+1 整除 N+1
: （只要计算奇数个素因子的乘积，再验算就行了）
: ...................
--
FROM 115.171.23.*