phi*_*idt 9 c algorithm performance
教授说这不是一个有效的算法来检查这个数字是否可以被100,000-150,000的数字整除.我找不到更好的方法.任何帮助,将不胜感激.
unsigned short divisibility_check(unsigned long n) {
unsigned long i;
for (i = 100000; i <= 150000; i++) {
if (n % i == 0) {
return 0;
}
}
return 1;
}
假设您需要确定正整数K是否可被100,000到150,000之间的数字整除，并且这种运算非常罕见，因此进行预计算只是不值得使用处理器时间或内存。
如果K <100,000，则不能将其除以100,000和150,000之间的数字。
如果100,000？ķ？150,000，它本身可以被整除。由您决定这是否重要。
如果K > 150,000被M除以100,000？M？150,000，ķ还必须是由整除大号 = ķ / 中号。这是因为K = L × M，并且所有三个都是正整数。因此，您只需要通过一组L来检验K的可除性，其中？K / 150,000？？L？？K / 100,000？。
但是，当K> = 15,000,000,000时，那组L s变得大于可能的M s 集合。然后，仅测试K对每个M的可除性就不再那么麻烦了，就像现在OP的代码一样。
当将此作为程序实现时，实际上，最重要的是添加的注释。不要编写描述代码功能的注释；编写注释，以解释您要实现的模型或算法（例如，在功能级别），以及您对每小段代码应该完成什么的意图。
在这种情况下，您可能应该if像上面我所做的那样在每个子句中添加一条注释，以解释您的推理。
初学者程序员通常会完全忽略注释。这很不幸，因为写出好的评论是事后难以养成的习惯。学习注释您的代码绝对是个好主意（正如我上文所述，描述代码的作用的注释没有什么用处；噪声多于帮助），并不断提高您的技能。
一个程序员的代码是可维护的，值得十个天才，他们生产只写代码。这是因为所有代码都有错误，因为人类会犯错误。要成为一名高效的开发人员，您的代码必须是可维护的。否则，您将不得不从头开始重写每个越野车零件，从而浪费大量时间。而且，正如您在上面看到的那样，在算法级别进行“优化”，即思考如何避免必须做的工作，比尝试优化循环或类似方法产生的结果要好得多。（您会发现，在现实生活中，经常出乎意料的是，以适当的方式优化循环可以完全消除循环。）
即使在练习中，正确的注释也可能是“没点，这没用”和“好吧，我会为此打个招呼，因为您有错别字/一处错误/一字不清”在第N行，但否则您的解决方案将有效”。
由于bolov不了解上述方法如何导致“ naive_with_checks”函数，因此我将在此处显示其实现方式。
为了便于测试，我将展示一个完整的测试程序。将要测试的整数范围和接受的除数范围作为程序的参数提供（即thisprogram 1 500000 100000 150000复制bolov的测试）。
#include <stdlib.h>
#include <inttypes.h>
#include <limits.h>
#include <locale.h>
#include <ctype.h>
#include <stdio.h>
#include <errno.h>
int is_divisible(const uint64_t number,
const uint64_t minimum_divisor,
const uint64_t maximum_divisor)
{
uint64_t divisor, minimum_result, maximum_result, result;
if (number < minimum_divisor) {
return 0;
}
if (number <= maximum_divisor) {
/* Number itself is a valid divisor. */
return 1;
}
minimum_result = number / maximum_divisor;
if (minimum_result < 2) {
minimum_result = 2;
}
maximum_result = number / minimum_divisor;
if (maximum_result < minimum_result) {
maximum_result = minimum_result;
}
if (maximum_result - minimum_result > maximum_divisor - minimum_divisor) {
/* The number is so large that it is the least amount of work
to check each possible divisor. */
for (divisor = minimum_divisor; divisor <= maximum_divisor; divisor++) {
if (number % divisor == 0) {
return 1;
}
}
return 0;
} else {
/* There are fewer possible results than divisors,
so we check the results instead. */
for (result = minimum_result; result <= maximum_result; result++) {
if (number % result == 0) {
divisor = number / result;
if (divisor >= minimum_divisor && divisor <= maximum_divisor) {
return 1;
}
}
}
return 0;
}
}
int parse_u64(const char *s, uint64_t *to)
{
unsigned long long value;
const char *end;
/* Empty strings are not valid. */
if (s == NULL || *s == '\0')
return -1;
/* Parse as unsigned long long. */
end = s;
errno = 0;
value = strtoull(s, (char **)(&end), 0);
if (errno == ERANGE)
return -1;
if (end == s)
return -1;
/* Overflow? */
if (value > UINT64_MAX)
return -1;
/* Skip trailing whitespace. */
while (isspace((unsigned char)(*end)))
end++;
/* If the string does not end here, it has garbage in it. */
if (*end != '\0')
return -1;
if (to)
*to = (uint64_t)value;
return 0;
}
int main(int argc, char *argv[])
{
uint64_t kmin, kmax, dmin, dmax, k, count;
if (argc != 5) {
fprintf(stderr, "\n");
fprintf(stderr, "Usage: %s [ -h | --help | help ]\n", argv[0]);
fprintf(stderr, " %s MIN MAX MIN_DIVISOR MAX_DIVISOR\n", argv[0]);
fprintf(stderr, "\n");
fprintf(stderr, "This program counts which positive integers between MIN and MAX,\n");
fprintf(stderr, "inclusive, are divisible by MIN_DIVISOR to MAX_DIVISOR, inclusive.\n");
fprintf(stderr, "\n");
return EXIT_SUCCESS;
}
/* Use current locale. This may change which codes isspace() considers whitespace. */
if (setlocale(LC_ALL, "") == NULL)
fprintf(stderr, "Warning: Your C library does not support your current locale.\n");
if (parse_u64(argv[1], &kmin) || kmin < 1) {
fprintf(stderr, "%s: Invalid minimum positive integer to test.\n", argv[1]);
return EXIT_FAILURE;
}
if (parse_u64(argv[2], &kmax) || kmax < kmin || kmax >= UINT64_MAX) {
fprintf(stderr, "%s: Invalid maximum positive integer to test.\n", argv[2]);
return EXIT_FAILURE;
}
if (parse_u64(argv[3], &dmin) || dmin < 2) {
fprintf(stderr, "%s: Invalid minimum divisor to test for.\n", argv[3]);
return EXIT_FAILURE;
}
if (parse_u64(argv[4], &dmax) || dmax < dmin) {
fprintf(stderr, "%s: Invalid maximum divisor to test for.\n", argv[4]);
return EXIT_FAILURE;
}
count = 0;
for (k = kmin; k <= kmax; k++)
count += is_divisible(k, dmin, dmax);
printf("%" PRIu64 "\n", count);
return EXIT_SUCCESS;
}
值得注意的是，上述运行bolov的测试，即thisprogram 1 500000 100000 150000在速度较慢的Core i5-7200U处理器上仅花费大约15毫秒的墙上时钟时间（13毫秒CPU时间）（中值）。对于真正大的数字，例如280,000,000,000到280,000,010,000，该测试将完成最大的工作量，并且在此计算机上每10,000个数字大约需要3.5秒。
换句话说，我不相信bolov的数字与正确编写测试用例的时间有任何关系。
重要的是要注意，对于介于1到500,000之间的任何K，bolov说他们的代码也用相同的测试进行度量，上面的代码最多进行两次可除性测试，以发现K是否可被100,000到150,000之间的整数整除。
因此，该解决方案非常有效。当测试的K相对较小（例如32位无符号整数或更小），或者无法使用预先计算的表时，这绝对是可接受的并且接近最佳。
即使可以使用预先计算的表，也不清楚素数分解是否/何时比直接检查更快。预计算表的大小和内容当然需要权衡。bolov声称它明显优于其他方法，但并未实施如上所示的适当“幼稚”可除性测试，并基于具有简单素数分解的非常小的整数（1到500,000）进行实验。
举例来说，预先检查整数1到500,000的除数表仅占用62500字节（对于150,000到500,000则占用43750字节）。使用该表，每个测试花费的时间几乎不变（这仅取决于内存和缓存的影响）。将其扩展到所有32位无符号整数将需要512 GiB（536,870,912字节）；该表可以存储在内存映射的只读文件中，以使OS内核可以随时管理将其映射到RAM的数量。
当试验分割的数量超出可能除数的范围（在这种情况下为50,000除数）时，质数分解本身（尤其是使用试验除法）会比单纯的方法昂贵。由于在1到150,000之间有13848个质数（如果将1和2数为质数），则对于足够大的输入值，尝试除法的数量可以很容易地接近除数的数量。
对于具有许多素数的数字，在组合阶段，发现是否有任何素数子集乘以100,000到150,000之间的数会更成问题。可能组合的数量增长快于指数增长。如果不进行仔细的检查，仅此阶段就可以为每个较大的输入数字完成更多的工作，而不仅仅是使用每个可能的除数进行尝试除法。
（例如，如果您有16个不同的素数，则您已经有65,535个不同的组合；这比直接试验除法的数量要多。但是，所有这样的数字都大于64位；最小的是2·3·5· 7·11·13·17·19·23·29·31·37·41·43·47·53 = 32,589,158,477,190,044,730，是65位数字。）
还有代码复杂性的问题。代码越复杂，调试和维护就越困难。
这是一个带有素数的递归方法。这里的想法是，如果一个数字可以被 100000 到 150000 之间的数字整除，则存在一条通过除法减少仅将通过目标范围内的状态的相关素数的乘积的路径。（注：下面的代码适用于大于 100000*150000 的数字）。在我的测试中，我找不到堆栈执行超过 600 次迭代的实例。
# Euler sieve
def getPrimes():
n = 150000
a = (n+1) * [None]
ps = ([],[])
s = []
p = 1
while (p < n):
p = p + 1
if not a[p]:
s.append(p)
# Save primes less
# than half
# of 150000, the only
# ones needed to construct
# our candidates.
if p < 75000:
ps[0].append(p);
# Save primes between
# 100000 and 150000
# in case our candidate
# is prime.
elif p > 100000:
ps[1].append(p)
limit = n / p
new_s = []
for i in s:
j = i
while j <= limit:
new_s.append(j)
a[j*p] = True
j = j * p
s = new_s
return ps
ps1, ps2 = getPrimes()
def f(n):
# Prime candidate
for p in ps2:
if not (n % p):
return True
# (primes, prime_counts)
ds = ([],[])
prod = 1
# Prepare only prime
# factors that could
# construct a composite
# candidate.
for p in ps1:
while not (n % p):
prod *= p
if (not ds[0] or ds[0][-1] != p):
ds[0].append(p)
ds[1].append(1)
else:
ds[1][-1] += 1
n /= p
# Reduce the primes product to
# a state where it's between
# our target range.
stack = [(prod,0)]
while stack:
prod, i = stack.pop()
# No point in reducing further
if prod < 100000:
continue
# Exit early
elif prod <= 150000:
return True
# Try reducing the product
# by different prime powers
# one prime at a time
if i < len(ds[0]):
for p in xrange(ds[1][i] + 1):
stack.append((prod / ds[0][i]**p, i + 1))
return False
输出：
c = 0
for ii in xrange(1099511627776, 1099511628776):
f_i = f(ii)
if f_i:
c += 1
print c # 239