我是Haskell的新手.
如何生成包含下一个整数的素因子的列表列表？
现在我只知道如何生成素数:
primes = map head $ iterate (\(x:xs) -> [y | y<-xs, y `mod` x /= 0 ]) [2..]
我想在C#2005中创建一个程序来计算给定输入的素因子.我想使用基本和最简单的东西,不需要为它创建方法也不需要为数组等事物创建简单的模数.有没有任何代码满足我的愿望？
这是用于查找简单因子的代码,我需要修改此代码以计算素因子
class Program
{
static void Main(string[] args)
{
int a, b;
Console.WriteLine("Please enter your integer: ");
a = int.Parse(Console.ReadLine());
for (b = 1; b <= a; b++)
{
if (a % b == 0)
{
Console.WriteLine(b + " is a factor of " + a);
}
}
Console.ReadLine();
}
}
我是python的新手,我对两个相对简单的代码块的性能感到困惑.第一个函数在给定素数列表的情况下生成数n的素数因子分解.第二个生成n的所有因子的列表.我会prime_factor比factors(对于相同的n)更快,但事实并非如此.我不是在寻找更好的算法,而是我想要理解为什么prime_factor这么慢factors.
def prime_factor(n, primes):
prime_factors = []
i = 0
while n != 1:
if n % primes[i] == 0:
factor = primes[i]
prime_factors.append(factor)
n = n // factor
else: i += 1
return prime_factors
import math
def factors(n):
if n == 0: return []
factors = {1, n}
for i in range(2, math.floor(n ** (1/2)) + 1):
if n % i == 0:
factors.add(i)
factors.add(n // i)
return list(factors)
使用timeit模块,
{ …
给定: set (),with .A = {a0, a1, ..., aN-1}1 ≤ N ≤ 1002 ≤ ai ≤ 500
问:找到所有A大小至少为2的子集的所有最小公倍数(LCM)的总和.
一组的LCM 被定义为最小整数,使得对于所有.B = {b0, b1, ..., bk-1}Bminbi | Bmin0 ≤ i < k
例:
让N = 3与A = {2, 6, 7},则:
LCM({2, 6}) = 6
LCM({2, 7}) = 14
LCM({6, 7}) = …algorithm primes computer-science dynamic-programming prime-factoring
我最近一直在阅读关于密码学中素因子的一般用法.在我读到的任何地方,它都表明没有"PUBLISHED"算法在多项式时间(与指数时间相反)中运行,以找到键的素因子.
如果发现或发布的算法确实在多项式时间内运行,那么这将如何影响现实世界的计算环境而不是理论和计算机科学的世界.考虑到我们依赖密码学的程度会突然停止.
考虑到这一点,如果P = NP是真的,那么可能会发生什么,我们依赖于它还有多少被推崇的事实.
我是初学者所以请原谅我的问题中的任何错误,但我想你会得到我的一般要点.
所以我只想找到给定数字的所有除数(除了数字本身).目前,我有这个:
public static List<int> proper_divisors(int x)
{
List<int> toreturn = new List<int>();
toreturn.Add(1);
int i = 0;
int j=1;
int z = 0;
while (primes.ElementAt(i) < Math.Sqrt(x))
{
if (x % primes.ElementAt(i) == 0)
{
toreturn.Add(primes.ElementAt(i));
toreturn.Add(x / primes.ElementAt(i));
j = 2;
z = (int)Math.Pow(primes.ElementAt(i), 2);
while (z < x)
{
if (x % z == 0)
{
toreturn.Add(z);
toreturn.Add(x / z);
j++;
z = (int)Math.Pow(primes.ElementAt(i), j);
}
else
{
z = x;
}
}
}
i++;
}
toreturn = …使用Python primefac模块时 - https://pypi.org/project/primefac/
我注意到这段代码有效:
import sys
import primefac
n = 600851475143
factors = list(primefac.primefac(n))
但这不是:
import sys
import primefac
n = 19087688894909892783503691960213776632781962588843842839953893606139157282825376128877238229887486797933180624979637419997128020864299273315243907454874577263432419226852240380380880131843664800828228959920799327101817796594944161768692639537839544009100224905464911818390882192901883104039350105285757995782376058970382205463192526628231366854662473466838863987148898819243940809068605863725041711337107340279029811816555169181781669826715177100102639379572663639848699896757952171115689208069972249342540932428107175784150214806633479073061672324629925288020557720111253896992657435200329511186117042808357973613389
factors = list(primefac.primefac(n))
导致以下错误:
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "C:\Python27\lib\site-packages\primefac.py", line 677, in primefac
f = multifactor(n, methods=methods, verbose=verbose)
File "C:\Python27\lib\site-packages\primefac.py", line 596, in multifactor
for p in procs: p.start()
File "C:\Python27\lib\multiprocessing\process.py", line 130, in start
self._popen = Popen(self)
File "C:\Python27\lib\multiprocessing\forking.py", line 277, in __init__
dump(process_obj, to_child, HIGHEST_PROTOCOL)
File …常数是均匀分配60的幂的数字.例如,60 2 = 3600 = 48×75,因此48和75都是60的幂的除数.因此,它们也是常规数.
这是四舍五入到下一个幂的延伸.
我有一个整数值N,它可能包含大的素因子,我想把它四舍五入到只由小素因子组成的数字(2,3和5)
例子:
f(18) == 18 == 21 * 32f(19) == 20 == 22 * 51f(257) == 270 == 21 * 33 * 51找到满足此要求的最小数字的有效方法是什么？
涉及的值可能很大,所以我想避免枚举从1开始的所有常规数字或维护所有可能值的数组.
algorithm math prime-factoring hamming-numbers smooth-numbers
我的理解是,目前许多公钥加密算法都依赖于大质数来构成密钥,并且难以将两个素数的乘积分解,使加密难以破解.我的理解是,将如此大的数字分解的原因之一是,使用数字的绝对大小意味着没有CPU可以有效地操作数字,因为我们的32位和64位CPU都不匹配对于1024,2048甚至4096位数.必须使用专门的Big Integer数学库来处理这些数字,并且这些库本质上很慢,因为CPU一次只能保存(和处理)小块(如32或64位).
所以...
为什么你不能用2048位寄存器和巨大的运算电路构建一个高度专业化的定制芯片,就像我们从8到16到32到64位CPU的缩放一样,只需构建一个更大的？该芯片不需要传统CPU上的大部分电路,毕竟它不需要处理虚拟内存,多线程或I/O等内容.它甚至不需要是支持存储指令的通用处理器.只是在最大数量上执行必要的算术计算的最低限度.
我不太了解IC设计,但我确实记得了解逻辑门如何工作,如何构建半加器,全加器,然后将一堆加法器链接在一起进行多位算术.只是扩大规模.很多.
现在,我很确定有一个非常好的理由(或者17)以上内容不起作用(因为否则会比我更聪明的人中的一个人已经做过了)但我有兴趣知道为什么它不会起作用.
(注意:这个问题可能需要一些重新工作,因为我甚至不确定这个问题是否有意义)
theory cpu-architecture bignum digital-design prime-factoring
似乎有几种真正快速的素数因子分解算法(一种看似理想的是二次筛分).但是,为了简单起见,我想使用现成的库,而不是自己(可能很差)实现.
我需要能够有效地计算多达15位的整数.正因为如此,我不找那一定尺度渐近最好的,因为我们可以假设被分解的数字是不到10算法15.
我已经看过维基百科的Quadratic Sieve页面上列出的一些实现.但是,有些实现似乎没有得到很好的维护; 有些人没有文件; 等等!我检查了一些着名的库,比如Boost,是否有分解方法,但似乎没有.
任何人都可以推荐符合上述标准的图书馆吗？