这是非常愚蠢的方式:
def divisorGenerator(n):
for i in xrange(1,n/2+1):
if n%i == 0: yield i
yield n
我想得到的结果类似于这个,但我想要一个更聪明的算法(这个太慢和愚蠢了:-)
我可以足够快地找到素数因子及其多样性.我有一个以这种方式生成因子的生成器:
(factor1,multiplicity1)(factor2,multiplicity2)
(
factor3,multiplicity3)
等......
即输出
for i in factorGenerator(100):
print i
是:
(2, 2)
(5, 2)
我不知道这对我想做什么有用多少(我将其编码用于其他问题),无论如何我想要一个更聪明的方法来制作
for i in divisorGen(100):
print i
输出这个:
1
2
4
5
10
20
25
50
100
更新:非常感谢Greg Hewgill和他的"智能方式":)计算所有100,00000的除数用他的方式对着我的机器上的愚蠢方式的39s,非常酷:D
更新2:停止说这是这篇文章的副本.计算给定数的除数数不需要计算所有除数.这是一个不同的问题,如果你认为它不是在维基百科上寻找"除数函数".在发布之前阅读问题和答案,如果你不明白什么是主题,只是不添加没有用的已经给出的答案.
我一直在努力学习生成素数的算法,我在维基百科上遇到了阿特金的Sieve.我理解算法的几乎所有部分,除了少数几个.以下是问题:
以下是维基百科的伪代码供参考:
// arbitrary search limit
limit ? 1000000
// initialize the sieve
for i in [5, limit]: is_prime(i) ? false
// put in candidate primes:
// integers which have an odd number of
// representations by certain quadratic forms
for (x, y) in [1, ?limit] × [1, ?limit]:
n ? 4x²+y²
if (n ? limit) and (n mod 12 = 1 or …我正在尝试用Java编写一个函数,它将返回特定数字所具有的因子数.
应考虑以下限制.
这是我到目前为止所做的,但它非常慢.
public static int getNumberOfFactors(BigInteger number) {
// If the number is 1
int numberOfFactors = 1;
if (number.compareTo(BigInteger.ONE) <= 0) {
return numberOfFactors;
}
BigInteger boundry = number.divide(new BigInteger("2"));
BigInteger counter = new BigInteger("2");
while (counter.compareTo(boundry) <= 0) {
if (number.mod(counter).compareTo(BigInteger.ZERO) == 0) {
numberOfFactors++;
}
counter = counter.add(BigInteger.ONE);
}
// For the number it self
numberOfFactors++;
return numberOfFactors;
}
问题:我正在尝试重构此算法以使其更快.什么是速度的第一次重构？
public int GetHowManyFactors(int numberToCheck)
{
// we know 1 is a factor and the numberToCheck
int factorCount = 2;
// start from 2 as we know 1 is a factor, and less than as numberToCheck is a factor
for (int i = 2; i < numberToCheck; i++)
{
if (numberToCheck % i == 0)
factorCount++;
}
return factorCount;
}
我需要计算数字 N 的除数总数（不关心除数的值是多少），并对所有这些数字 N 在 40-80 次运算内完成。我该怎么做？这不是一个家庭作业问题。我尝试了Pollard 的 Rho算法，但即使这样对于我的目的来说也太慢了。这是我的 python 代码。如果可能的话，我该如何提高其性能？
def is_prime(n):
if n < 2:
return False
ps = [2,3,5,7,11,13,17,19,23,29,31,37,41,
43,47,53,59,61,67,71,73,79,83,89,97]
def is_spsp(n, a):
d, s = n-1, 0
while d%2 == 0:
d /= 2; s += 1
t = pow(int(a),int(d),int(n))
if t == 1:
return True
while s > 0:
if t == n-1:
return True
t = (t*t) % n
s -= 1
return False
if n in ps: return True
for p …如何找到除数最多的1到100范围内的最小数字？我知道一个简单的方法是检查每个数字的除数从1到100并跟踪具有最大除数的数字.但是有更有效的方法吗？
试图将用Python编写的一些方法转换为C#.这条线看起来像这样:
d[p] = d.setdefault(p, 0) + 1
setdefault究竟做了什么？我可以在C#字典中使用类似的东西吗？或者更确切地说,我如何将该行转换为C#？
整体问题:项目欧拉12 - 第一个三角形数值超过500个除数的值是多少？
问题的焦点:除数函数
语言:Python
描述:我使用的函数是粗暴的,程序找到一个除数比x更多的除数所需的时间几乎呈指数增长,每10或20个数字更高.我需要达到500或更多的除数.我已经确定了除数函数正在减少程序.我做的研究让我得到了除数函数,特别是除数函数,它应该是一个函数,它将计算任何整数的所有除数.我看过的每一页似乎都是针对数学专业的,我只有高中数学.虽然我确实遇到过一些提到关于素数和阿特金斯筛选的页面,但是我无法在素数之间建立连接并找到任何整数的所有除数,也没有在网上找到任何关于它的东西.
主要问题:有人可以解释如何编码除数函数甚至提供样本吗？当我用代码查看它们时,数学概念对我来说更有意义.非常感谢.
蛮力除数功能:
def countdiv(a):
count = 0
for i in range(1,(a/2)+1):
if a % i == 0:
count += 1
return count + 1 # +1 to account for number itself as a divisor
给定数字N,必须找到所有i的除数,其中i> = 1且i <= N. 无法理解.我是否需要使用素数分解？限制为N <= 10 ^ 9样本输出:
1 --> 1
2 --> 3
3 --> 5
4 --> 8
5 --> 10
6 --> 14
7 --> 16
8 --> 20
9 --> 23
10 --> 27
11 --> 29
12 --> 35
13 --> 37
14 --> 41
15 --> 45
所以我一直在尝试通过解决 Codeforce 上的一些问题来学习 Haskell。
即使我认为我的时间复杂度是最佳的，我也得到了很多 TLE（超出时间限制）。
我的问题是：是我编写这个程序的方式使它变慢了吗？
例如，这里是问题。
基本上答案是找到给定的，其中
and =和之间的除数数之差。annan = 2*an-1 + D(n)D(n)nn-1
（更新：上限为n10 6）。
下面是我的程序。
import qualified Data.Map.Strict as Map
main = do t <- read <$> getLine
putStrLn . show $ solve t
solve :: Integer -> Integer
solve 0 = 1
solve 1 = 1
solve n = (2*(solve (n-1)) + (fact n) - (fact (n-1))) `mod` 998244353
where fact …