我试图找到可以被 1 到 20 的所有数字整除的最小正数。
我首先创建了一个从数字 1 到 20 运行的 for 循环，然后我知道我必须创建另一个循环，如果这两个数字的模不是 0，则将某个数字除以 1 到 20 之间的每个数字，然后跳到下一个数字（即增加 1），直到找到最小的数字。
public class Problem5 {
public static void main(String args[]){
for(int i=1;i<=20;i++){
for(int counter=1;variable length argument?;counter++){
if(i%counter==0){
System.out.println(counter);
}
}
}
}
}
我知道我需要第二个 for 循环才能从 1 计数到我需要的任何数字，所以我是否需要一个可变长度参数，因为我不知道最小的数字是多少？
答案很容易计算，无需暴力迭代所有整数，直到找到答案：
Num Factors
2 2
3 3
4 2 already have one '2', need only one more
5 5
6 already have 2 & 3
7 7
8 2 already have 2 '2's, need only one more
9 3 already have one '3', need only one more
10 already have 2 and 5
11 11
12 already have 2 '2's and a '3'
13 13
14 etc...
15
16 2
17 17
18
19 19
20
将第二列中的所有数字相乘。Java 中的实现留作练习。
你需要反过来循环，如果你愿意，你不需要检查是否% 1 可以使用最高的素数。如果它是 4 和 5 的倍数，它也必须是 20 的倍数；）
由于它必须是所有素数的倍数，您只需检查 2*3*5*7*11*13*17*19 的倍数。这将使它变得更快，更快。
没有上限，所以你不需要添加一个。counter < Integer.MAX_VALUE如果你愿意，你可以做到。
您可以计算这些因素必须是什么，而不是使用蛮力。
public class CommonMultipleMain {
static final int MAX = Integer.getInteger("max", 1000);
public static void main(String... ignored) {
// warmup
getLowestMultipleOf(60);
long start = System.nanoTime();
BigInteger bi = getLowestMultipleOf(MAX);
long time = System.nanoTime() - start;
System.out.println("Smallest number which has factors up to " + MAX + " took " + time / 1000 + " us, is " + bi);
}
private static BigInteger getLowestMultipleOf(int max) {
int[] maxFactorCount = new int[max + 1];
for (int i = 2; i <= max; i++) {
int[] factors = getFactorsFor(i);
for (int j = 2; j < factors.length; j++)
if (maxFactorCount[j] < factors[j])
maxFactorCount[j] = factors[j];
}
BigInteger bi = BigInteger.ONE.shiftLeft(maxFactorCount[2]);
for (int i = 3; i <= max; i += 2) {
int exponent = maxFactorCount[i];
switch (exponent) {
case 0:
break;
case 1:
bi = bi.multiply(BigInteger.valueOf(i));
break;
default:
bi = bi.multiply(BigInteger.valueOf(i).pow(exponent));
break;
}
}
return bi;
}
private static int[] getFactorsFor(int i) {
int[] factors = new int[i + 1];
while ((i & 1) == 0) {
i >>= 1;
factors[2]++;
}
for (int j = 3; j * j <= i; j += 2) {
while (i % j == 0) {
i /= j;
factors[j]++;
}
}
if (i > 1)
factors[i]++;
return factors;
}
}
印刷
Smallest number which has factors up to 1000 took 15005 us, is 7128865274665093053166384155714272920668358861885893040452001991154324087581111499476444151913871586911717817019575256512980264067621009251465871004305131072686268143200196609974862745937188343705015434452523739745298963145674982128236956232823794011068809262317708861979540791247754558049326475737829923352751796735248042463638051137034331214781746850878453485678021888075373249921995672056932029099390891687487672697950931603520000
计算到这个数字需要比宇宙年龄更长的时间，但通过计算，它所用的时间比眨眼所用的时间要少。
int eulersmallestNumber(int value){
int start = 1;
boolean found = false;
while(!found){
found = eulerhelper(start,value);
start++;
}
return start;
}
boolean eulerhelper(int start, int value){
for(int i=1;i<=value;i++){
if(i%start != 0) return false;
}
return true;
}
你给eulersmallestNumber一个你希望它循环的最大数量，例如 10。
它将解决这个问题。
2520 是可以除以 1 到 10 的每个数字而没有任何余数的最小数字。
这个怎么运作。
它从起始值 1 递增并调用函数 eulerhelper，该函数返回一个布尔值。（一旦 eulerhelper 返回 true，while 循环将退出）
eulerhelper 获取值并除以所有值1 - value。如果其中一个值有提醒，则返回 false。但是，如果这些数字之间的所有值都没有提醒，它将返回 true。
从您的方法开始，您需要一直到 i/2（或理想情况下是 sqrt(i)）。所以我们会得到（我们跳过那些）：
（编辑：修改和更正的代码）
int i,j,mult;
int smallest = 2; // Start with 2
for (i = 3; i <= 20; i++)
{
if (smallest % i == 0) // Already divisible
continue;
mult = i;
// We try to divide every number from 2 to 20 with
// the numbers before it, so that we skip repeating
// prime factors and get the smallest numbers
for (j = 2; j <= sqrt(i); j++)
{
// j too high
if (mult / j == 0)
break;
if (mult % j == 0)
mult /= j;
}
// mult will be 1 if the current number is a product
// of 2 or more numbers before it
smallest *= mult;
}
printf("%d\n", smallest);
它是C，但你应该理解它就好了。为了检查，取从 1 到 20 的所有数字并写出它们的素数分解。然后取所有最高幂的素数并将它们相乘。应该是 232792560