项目Euler：问题1（可能的重构和运行时优化）
我听过很多关于Project Euler的消息，所以我想我解决了C＃中的一个问题。 网站上所述的问题如下：
如果我们列出10以下的所有自然数是3或5的倍数，我们得到3,5,6和9.这些倍数的总和是23。
求出1000以下3或5的所有倍数的总和。
我编写了如下代码：
class EulerProblem1 { public static void Main() { var totalNum = 1000; var counter = 1; var sum = 0; while (counter < totalNum) { if (DivisibleByThreeOrFive(counter)) sum += counter; counter++; } Console.WriteLine("Total Sum: {0}", sum); Console.ReadKey(); } private static bool DivisibleByThreeOrFive(int counter) { return ((counter % 3 == 0) || (counter % 5 == 0)); } } 能够以更少的冗长/更清晰的语法和更好的优化来获得关于替代实现的一些想法将会很棒。 这些想法可能会有所不同，从快速和肮脏到带出大炮灭绝蚊子。 目的是探索计算机科学的深度，同时尝试改进这个特别琐碎的代码片段。
谢谢
使用LINQ（根据评论中的建议更新）
static void Main(string[] args) { var total = Enumerable.Range(0,1000) .Where(counter => (counter%3 == 0) || (counter%5 == 0)) .Sum(); Console.WriteLine(total); Console.ReadKey(); }
更新为不重复计算3和5的倍数的数字：
int EulerProblem(int totalNum) { int a = (totalNum-1)/3; int b = (totalNum-1)/5; int c = (totalNum-1)/15; int d = a*(a+1)/2; int e = b*(b+1)/2; int f = c*(c+1)/2; return 3*d + 5*e - 15*f; }
这是我原来的F＃解决方案到C＃的音译。 编辑：它基本上是mbeckish的解决方案作为循环而不是函数（我删除了双重计数）。 我喜欢mbeckish更好。
static int Euler1 () { int sum = 0; for (int i=3; i<1000; i+=3) sum+=i; for (int i=5; i<1000; i+=5) sum+=i; for (int i=15; i<1000; i+=15) sum-=i; return sum; }
这是原始的：
let euler1 d0 d1 n = (seq {d0..d0..n} |> Seq.sum) + (seq {d1..d1..n} |> Seq.sum) - (seq {d0*d1..d0*d1..n} |> Seq.sum) let result = euler1 3 5 (1000-1)
我有一段时间没有编写任何Java，但是这应该在很短的时间内以恒定的时间解决它：
public class EulerProblem1 { private static final int EULER1 = 233168; // Equal to the sum of all natural numbers less than 1000 // which are multiples of 3 or 5, inclusive. public static void main(String[] args) { System.out.println(EULER1); } }
编辑：这是一个C实现，如果每条指令都重要：
#define STDOUT 1 #define OUT_LENGTH 8 int main (int argc, char **argv) { const char out[OUT_LENGTH] = "233168\n"; write(STDOUT, out, OUT_LENGTH); }
笔记：
-
write调用没有error handling。 如果需要真正的鲁棒性，则必须采用更复杂的error handling策略。 增加的复杂性是否值得更高的可靠性取决于用户的需求。 - 如果您有内存限制，则可以使用直接字符数组而不是由多余空字符终止的字符串来保存字节。 然而，在实践中，无论如何，
out几乎肯定会被填充到8个字节。 - 虽然可以通过将字符串内联放在
write调用中来避免out变量的声明，但任何真正的编译器都会优化声明。 -
writesyscall优先于puts或类似使用，以避免额外的开销。 从理论上讲，您可以直接调用系统调用，可能会节省几个周期，但这会引发重要的可移植性问题。 关于这是否是可接受的权衡，您的里程可能会有所不同。
重构@ mbeckish非常聪明的解决方案：
public int eulerProblem(int max) { int t1 = f(max, 3); int t2 = f(max, 5); int t3 = f(max, 3 * 5); return t1 + t2 - t3; } private int f(int max, int n) { int a = (max - 1) / n; return n * a * (a + 1) / 2; }
这与我解决问题的方式基本相同。 我知道在project-euler的论坛上还有其他解决方案（可能也更有效）。
一旦你输入你的答案回到问题，你就可以选择去论坛解决这个问题。 你可能想看看那里！
DivisibleByThreeOrFive中的代码如果您按如下方式声明它会稍快一些：
return ((counter % 3 == 0) || (counter % 5 == 0));
如果您不想依赖编译器来内联函数调用，您可以通过将此代码放入Main例程来自行完成。
你可以为此提出一个封闭的forms解决方案。 诀窍是寻找模式。 尝试列出总计为十或二十的术语，然后使用代数对它们进行分组。 通过进行适当的替换，您可以将其推广到十个以外的数字。 关注边缘情况。
在C中尝试这个。它是恒定的时间，并且只有一个除法（如果编译器没有优化div / mod，它应该是两个除法）。 我确信它可以让它更明显一点，但这应该有效。
它基本上将总和分为两部分。 大部分（对于N> = 15）是一个简单的二次函数，它将N分成15的精确块。较小的部分是不适合块的最后一位。 后一点比较麻烦，但只有少数可能性，因此LUT会立即解决它。
const unsigned long N = 1000 - 1; const unsigned long q = N / 15; const unsigned long r = N % 15; const unsigned long rc = N - r; unsigned long sum = ((q * 105 + 15) * q) >> 1; switch (r) { case 3 : sum += 3 + 1*rc ; break; case 4 : sum += 3 + 1*rc ; break; case 5 : sum += 8 + 2*rc ; break; case 6 : sum += 14 + 3*rc ; break; case 7 : sum += 14 + 3*rc ; break; case 8 : sum += 14 + 3*rc ; break; case 9 : sum += 23 + 4*rc ; break; case 10 : sum += 33 + 5*rc ; break; case 11 : sum += 33 + 5*rc ; break; case 12 : sum += 45 + 6*rc ; break; case 13 : sum += 45 + 6*rc ; break; case 14 : sum += 45 + 6*rc ; break; }
你可以这样做：
Func Euler = total=> new List() {3,5} .Select(m => ((int) (total-1) / m) * m * (((int) (total-1) / m) + 1) / 2) .Aggregate( (T, m) => T+=m);
你仍然有重复计算问题。 我会再考虑一下这个。
编辑：
这是LINQ中一个工作（如果稍微不优雅）的解决方案：
var li = new List() { 3, 5 }; Func Summation = (total, m) => ((int) (total-1) / m) * m * (((int) (total-1) / m) + 1) / 2; Func Euler = total=> li .Select(m => Summation(total, m)) .Aggregate((T, m) => T+=m) - Summation(total, li.Aggregate((T, m) => T*=m));
你们中的任何人都可以改进吗？
说明：
记住线性进展的求和公式是n（n + 1）/ 2。 在第一种情况下，你有3,5 <10的倍数，你需要Sum（3 + 6 + 9,5）。 设置total = 10，你得到一个整数序列1 ..（int）（total-1）/ 3，然后对序列求和并乘以3.你可以很容易地看到我们只是设置n =（int ）（total-1）/ 3，然后使用求和公式并乘以3.一个小代数给出了求和仿函数的公式。
我喜欢technielogys的想法，这是我对修改的想法
static int Euler1 () { int sum = 0; for (int i=3; i<1000; i+=3) { if (i % 5 == 0) continue; sum+=i; } for (int i=5; i<1000; i+=5) sum+=i; return sum; }
虽然也想到了可能是一个小的启发式，这有什么改进吗？
static int Euler1 () { int sum = 0; for (int i=3; i<1000; i+=3) { if (i % 5 == 0) continue; sum+=i; } for (int i=5; i<250; i+=5) { sum+=i; } for (int i=250; i<500; i+=5) { sum+=i; sum+=i*2; sum+=(i*2)+5; } return sum; }
Your approach is brute force apprach, The time complexity of the following approach is O(1), Here we are dividing the given (number-1) by 3, 5 and 15, and store in countNumOf3,countNumOf5, countNumOf15. Now we can say that 3 will make AP, within the range of given (number-1) with difference of 3. suppose you are given number is 16, then 3=> 3, 6, 9, 12, 15= sum1=>45 5=> 5, 10, 15 sum2=> 30 15=> 15 => sum3=15 Add sum= sum1 and sum2 Here 15 is multiple of 3 and 5 so remove sum3 form sum, this will be your answer. **sum=sum- sum3** please check link of my solution on http://ideone.com/beXsam] import java.util.*; class Multiplesof3And5 { public static void main(String [] args){ Scanner scan=new Scanner(System.in); int num=scan.nextInt(); System.out.println(getSum(num)); } public static long getSum(int n){ int countNumOf3=(n-1)/3;// int countNumOf5=(n-1)/5; int countNumOf15=(n-1)/15; long sum=0; sum=sumOfAP(3,countNumOf3,3)+sumOfAP(5,countNumOf5,5)-sumOfAP(15,countNumOf15,15); return sum; } public static int sumOfAP(int a, int n, int d){ return (n*(2*a +(n -1)*d))/2; } }
new List{3,5}.SelectMany(n =>Enumerable.Range(1,999/n).Select(i=>i*n)) .Distinct() .Sum()
[更新]（响应评论要求解释这个algorothm）这为每个基值（在这种情况下为3和5）构建了一个扁平的倍数列表，然后删除重复（例如，在这种情况下，多个可被整除的地方，通过3 * 5 = 15）然后将剩余值相加。 （与我在这里看到的任何其他解决方案相比，这对于拥有两个以上的基本值IMHO来说也很容易理解。）