2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
So nice and easy. Here's my solution in C. It only took 20 lines :D
#include <stdio.h>
int main()
{
int i=1;
while(1)
{
if(i%11==0 && i%12==0 && i%13==0
&& i%14==0 && i%15==0 && i%16==0
&& i%17==0 && i%18==0 && i%19==0
&& i%20==0)
{
printf("%d\n", i);
return 0;
}
i++;
}
return 0;
}
Execution Time: 1.859 s
The execution time is horribly slow so if anyone wants to comment on how to make it quicker, be my guest!
NotMyFault
Hello, I know that it is a year after your post, but I just recently got into project Euler. Your solution does work, but I have improved on it.
ReplyDeleteThe only things that I have done differently are:
I changed the order of the modulus checking. Because, while using AND logic, the execution stops once it reaches a false result in the comparisons, I wrote the prime numbers first (My order was 17, 19, 13, 11, 12, 14, 15, 16, 18, 20.) This decreases execution time by reducing the number of operations.
Also, I incremented by 2520 instead of 1. You know that the final solution must be a multiple of 2520, because it is the smallest for the numbers 1..10.
I generally get an execution speed of .002 seconds (on my i7-2460QM beast :D)
wow, nice optimization! the incrementation by 2520 is really nice :D thanks for this
ReplyDelete-NotMyFault
Hello
ReplyDeleteI think it is not good to increment by 2520. I think it is pointless.
The main goal of the task is to find out the value that you don't know.
So I think it is good to use an array for the solution.
Here I present my solution.
My running time is 0m0.008s (Mac OS, Intel Core 2Duo 2GHz, RAM 4GB DDR3)
Check this out!
#include
#include
#define SIZE 9
main()
{
int i, index = 0;
long long num = 0;
//create an array of numbers and initialize it
int *massiv = malloc(SIZE * sizeof(int));
for(i = 1; i <= SIZE; i++) massiv[i] = i;
//find a number
while(1){
num += 20;
for(i = 1; i <= SIZE; i++){
if(num % massiv[i] == 0) index++;
else{
index = 0;
break;
}
}
if(index == 9) break;
}
free(massiv);
printf("%lld\n", num);
return 0;
}
The libraries are: stdio.h and stdlib.h
ReplyDeleteTo resolve the Euler real task just start with i=11
ReplyDeleteI just got into this website, so sorry for the response years later xD. Another tip for optimizing is keep in mind that it must be a multiple of 20 so increasing by just 1 is pointless. You might as well increase by 20, and as someone else said start at 2520.
ReplyDelete