Euler Program in Java

Question

I just started by solving Project Eulers problems. Although it is very simple. I want to express my opinion on the best solution.

Problem :

If we list all natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all multiples of 3 or 5 below 1000.

This is how I encoded it:

package com.problem.one.ten; public class NaturalNumber { public static void main(String args[]) { int sum=0; for(int i=0; i<1000; i++) { if((i%3 == 0) || (i%5 == 0)){ sum += i; } } System.out.println(sum); } } 

Answer 1

This looks good, although I would put sum in main. This is not very important for such a simple program. But in general, you should declare variables in the narrowest possible scope.

Answer 2

The best solution is to simply apply the inclusion-exclusion principle. The sum of all the numbers we are interested in is equal to (1) the sum of all numbers divisible by 3, plus (2) the sum of all numbers divisible by 5, minus (3) the sum of all numbers divisible by 15. Each of the 3 sums is the sum of the arithmetic progression which is relatively easy to find. Basically, you do not need a loop.

The number of non-negative integers divisible by n below N is exactly [[N - 1) / n] + 1. The maximum number is n * ([(N - 1) / n], so by (N - 1) / n ] * ([(N - 1) / n] + 1) * n / 2.

In our case, we received:

• N = 1000, n = 3, [(N - 1) / n] = 333, sum = 333 * 334 * 3/2.
• N = 1000, n = 5, [(N - 1) / n] = 199, sum = 199 * 200 * 5/2.
• N = 1000, n = 15, [(N - 1) / n] = 66, sum = 66 * 67 * 15/2.

The end result is 233168.

Perhaps there is an even better solution.

Answer 3

Although I am sure that there is an O (1) solution for this problem, clarifying this would not be practical, given that you were asked to provide an answer of 1000.

I agree with Matthew that the sum should be a local variable, but otherwise your code also looks good.

solution without code (just for fun):

Using the fact that sum(1+2+3+...+n) = n(n+1)/2 , we can get that the sum of multiples of x below 1000 is floor(1000/x)*(floor(1000/x)+1)/2*x .

The answer we need is the sum of multiples of 3 below 1000, plus the sum of multiples of 5, minus the sum of multiples of 15 (which would otherwise be double).

There are 999/3 = 333 times 3 below 1000, 999/5 = 199 times 5 below 1000, and 999/15 = 66 times 15 below 1000

So, the sum of all multiples of 3 is below 1000 = 333 * 334/2 * 3 = 166833, the sum of multiples of 5 is below 1000 = 199 * 200/2 * 5 = 99500, and the sum of multiples of 15 is below 1000 = 66 * 67/2 * 15 = 33165

Response execution 166833 + 99500 - 33165 = 233168

Answer 4

Your solution is logically simple and therefore the easiest to check. The most effective analytical solutions, such as Vlad and Luke.

But for what it's worth, my first thought when I saw the problem:

 public int doit() { int sum=0; for (int n=0;n<1000;n+=3) { sum+=n; } for (int n=0;n<1000;n+=5) { if (n%3!=0) // Don't pick up the 3 twice sum+=n; } return sum; } 

That would be more efficient than your solution, as it skips numbers that we know we are not interested in. And it's still intuitive how this works.

A solution without a loop is better, but I publish it only because I have a meeting in 5 minutes, and I'm already here.

Answer 5

I did this using arithmetic progression with O (1). Here is my solution, and it worked for values ​​greater than 1000, up to 10 ^ 9, for example

 long sum1=0,sum2=0,sum3=0,sum=0; long no3=0,no5=0,no15=0; //find the no of terms no3=(array[i]-1)/3; no5=(array[i]-1)/5; no15=(array[i]-1)/15; //find the sum of the terms sum1=no3*(6+(no3-1)*3)/2 ; sum2=no5*(10+(no5-1)*5)/2; sum3=no15*(30+(no15-1)*15)/2; sum=sum1+sum2-sum3; System.out.println(sum); } 

Answer 6

For Project Euler, I have one piece of advice: go into the functionality.

I previously solved about 100 problems in Java, but I struggled a lot with them along the way, and I had to write a lot of library code. I recently started solving them in Scala starting from Problem 1, and it seems more natural.

Besides the fact that you can solve the first few problems with just pens and paper, as indicated in other answers, solving this problem using a functional language is very simple and easy. This is my solution from problem 1:

 object Problem001 { def main(args: Array[String]) = println(find(1000)) def find(max:Int) = Stream.from(1) filter (n => n % 3 == 0 || n % 5 == 0) takeWhile (_ < max) sum } 

Answer 7

Rules decision Vlad.
But here's another line by line that Jay wrote, but with 1 loop

 def ProjectEuler1(upper_limit): num_3mult = (upper_limit-1)//3 # total multiples of 3, less than upper_limit num_5mult = (upper_limit-1)//5 # total multiples of 5, less than upper_limit sum_multiples = 0 for i in range(1,num_3mult+1): sum_multiples += i*3 if i <= num_5mult and i%3!=0: # only add the multiples of 5 which are not multiple of 3 (to avoid adding duplicates) sum_multiples += i*5 print('Sum of all multiples of 3 and 5 below 1000 = ', sum_multiples, end='\n') ProjectEuler1(1000) 

Answer 8

I solved the problem and came up with the solution @vlad said. I am delighted with this (I never heard of the principle of inclusion-exclusion). Here is my code:

 public class Prob1 { public static int sumOfMultiples(int i, int j, int limit){ int s = --limit / i, t = limit / j, u = limit / (i * j); return (i*(s*(s+1)/2)) + (j*(t*(t+1)/2)) - ((i*j)*(u*(u+1)/2)); } } 

Test:

 public class TestProb1 { @Test public void testSumOfMultiples(){ int actual = Prob1.sumOfMultiples(3, 5, 10); assertEquals(23, actual); actual = Prob1.sumOfMultiples(3, 5, 30); assertEquals(195, actual); actual = Prob1.sumOfMultiples(3, 5, 1000); assertEquals(233168, actual); } } 

Answer 9

You can solve this in .NET with a single LINQ expression

 Dim sum = (From num In Enumerable.Range(1, 999) Where num Mod 3 = 0 OrElse num Mod 5 = 0 Select num).Sum() 

Answer 10

Well, the obvious arithmetic section is as follows:

 int s=0,n,N=1000; n=(N-1)/ 3; s+= 3*n*(n+1); n=(N-1)/ 5; s+= 5*n*(n+1); n=(N-1)/15; s-=15*n*(n+1); s>>=1; // can further optimize by precomputing N-1, n+1 to some temp vars // also multiplication can be shift added instead 

I saw some crazy things here, and why the hell are you people

• use division for suma ???
• use +1 increment for multipliers + 3i and + 5i.

try this instead:

 int s=0,N=1000; for (int i=0;i<N;i+=5) s+=i; for (int i=0,j=0;i<N;i+=3,j++) if (j==5) j=0; else s+=i; 

I know it is trivial, but I hope it helps someone understand how to write better.

Answer 11

Week 5 of my first JAVA course ... that's how I solve it;) this is the real thing of triumph

 import java.util.Scanner; public class Counter { public static void main(String args[]) { System.out.println("Enter an integer, and COUNTER will find the sum of all the multiples of THREE and FIVE:"); int entry; Scanner input = new Scanner(System.in); entry = input.nextInt(); int three = 0; int threeOut = 0; int threeOpTot = (entry / 3); int threeOp = 0; while( threeOp < threeOpTot) { three = three + 3 ; threeOut = three + threeOut ; threeOp += 1; System.out.println(threeOp + " times 3 is " + three + ". "); System.out.println(" " + threeOut + ", is the total sum of " + threeOp + "/" + threeOpTot + " threes"); } int five = 0; int fiveOut = 0; int fiveOpTot = (entry / 5); int fiveOp = 1; while( fiveOp < fiveOpTot) { five = five + 5 ; fiveOut = five + fiveOut ; fiveOp += 1 ; System.out.println(threeOp + " times 3 is " + three + ". "); System.out.println(" " + threeOut + ", is the total sum of " + threeOp + "/" + threeOpTot + " threes"); } int fifteen = 0; int fifteenOut = 0; int fifteenOpTot = (entry / 15); int fifteenOp = 0; while( fifteenOp < fifteenOpTot) { fifteen = fifteen + 15 ; fifteenOut = fifteen + fifteenOut ; fifteenOp += 1 ; System.out.println(fifteenOp + " times fifteen is " + fifteen + "."); System.out.println(" " + fifteenOut + ", is the total sum of " + fifteenOp + "/" + fifteenOpTot + " fifteens"); } System.out.println("The final values of threes' are " + (threeOut) ); System.out.println("The final values of five' are " + (fiveOut) ); System.out.println("The sum of the over-lapping 15 factors are " + (fifteenOut) ); System.out.println("Grand total: " + (fiveOut + threeOut - fifteenOut) ); } } 

Answer 12

This algorithm will work fine, but you do not think that this is not an optimal algorithm.

Here, the simple logic of finding a sum of n elements would do the trick, and this algorithm would work on huge data as well.

Here is a snippet of code from my program on my CodeForWin blog - Project Euler 1: Multiples of 3 and 5

 n--; //Since we need to compute sum of multiples below n if(n>=3) { totalElements = n/3; sum += (totalElements * ( 3 + totalElements*3)) / 2; } //Check if n is more than or equal to 5 then compute sum of all elements //divisible by 5 and add to sum. if(n >= 5) { totalElements = n/5; sum += (totalElements * (5 + totalElements * 5)) / 2; } //Check if n is more than or equal to 15 then compute sum of all elements //divisible by 15 and subtract from sum. if(n >= 15) { totalElements = n/15; sum -= (totalElements * (15 + totalElements * 15)) / 2; } System.out.println(sum); 

This algorithm computes sum of n=1000000000000 in a fraction of milliseconds.

Answer 13

 public static void main(String[] args) { int sum = 0; int i = 0; while (i < 1000) { if (i % 3 == 0 || i % 5 == 0) { sum = sum + i; } i++; } System.out.println("Sum is " + sum); }