# Project Euler #5: Smallest multiple

# Project Euler #5: Smallest multiple

tilper + 12 comments Pro tip: M is divisible by all numbers from 1 to N iff M is equal to the product of all prime powers p^k where p is prime and divides M, and p < N, and k is the largest integer such that p^k < N. For example, 2520 = 2^3 * 3^2 * 5 * 7.

Aniruddha_ + 0 comments [deleted]zerodivisible + 4 comments Out of curiosity, is there a name of this theorem? I must say it's an interesting one, definitely will simplify the implementation of this algorithm.

shashank21jHackerRank AdminChallenge Author + 6 comments It's a simple observation and quite a nice one.

It's clear that N needs to be divisible by primes < NNow k can be determined by the fact that N lies between p^k and p^(k+1) and any number between p^k and N doesn't need to be divisible by p^(k+1)

so you just need k, where p^k < N.

kherashanu + 0 comments please see why my code is wrong. sort discussion by recent

tenzin392 + 1 comment hello Moderator, is there a reason why i/o of test cases aren't visible for us? it would help us greatly if we see where we are wrong to solve a method that we intuitively think of. (I guess it is because you fear some programmers manually output depending on a sample to pass the test cases?)

detritusonice + 0 comments Test cases are not available during live contests due to the reason you mention, and this is a perpetually live one. You could assert some hypotheses about the input to get an idea for some testcase you fail. But then again i am no moderator.

harshahj97 + 1 comment Why cant p^k be equal to N??

felix_m_roberts1 + 0 comments Perfectly possible, but doesn't change anything

sayamqazi + 0 comments a small change p^k <= N

dmitry_r + 0 comments Hi shashank,

I suggest you edit/extend the test cases. I've just submitted solution where the product (smallest multiple) was computed as 32bit int and I've passed all the test cases despite the fact that the product overflowed and the answer was wrong (see my first submission). Only later, I've played around with it and custom inputs and discovered that I need int64

Cheers, Dmitry

K_Abhishek + 0 comments really a good idea

tilper + 2 comments No name as far as I know.

moremeds + 0 comments awesome!

sayamqazi + 1 comment It is called prime factorization. There exists only one unique prime factorization for any given number. See wikipedia "Prime factorization".

tilper + 0 comments I know about prime factorization. The question was whether the specific property that uses prime factorization has a name. It doesn't, as far as I know.

Bogdan_D + 1 comment Actually is is called

**The Fundamental Theorem of Arithmetic**Any integer greater than 1 is either a prime number, or can be written as a unique product of prime numbers (ignoring the order).Here!tilper + 0 comments The statement I originally mentioned is most certainly not the Fundamental Theorem of Arithmetic, but it is slightly related.

AnastasiaP + 0 comments yes, every positive integer can be represented as a

*unique*product of primes. It is known as "Fundamental Theorem of Arithmetic" or "Unique Prime Factorization Theorem" https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmeticThat's also why 1 is not a prime number (2 is the smallest prime), because it would contradict the uniqueness (i.e. 6 is product of unique primes: 3 x 2. It is not 3 x 2 x 1 or 3 x 2 x 1 x 1, etc)

octanetwisted + 0 comments wow, i have been banging my head in the wrong direction all along. Nice observation.

nikhil_nagaraju + 0 comments I thought of finding LCM for 1 to N numbers, but this is simpler.

Furcifer + 1 comment This is a really cool observation :-) But what will be the time complexity of this one? The LCM solution is O(N*log(N)) approximately. Here, for this solution is it pi(N)*log(N) = O(N) approx.

thebongy + 1 comment You can store primes upto 40 using the Sieve of Eratosthenes, in a list X. Supposing the largest prime less than (or equal to) a given input N is the 'P'th prime, then the answer is given by:

All of this combined gives a complexity of approximately O(N/log(N)) (An Approximation of the prime number thoerem) (Also assuming that log and pow are constant time functions)

Here is a C++ implementation:

#include <iostream> #include <vector> #include <cmath> using namespace std; typedef long long ll; int logarithm(int base, int x) { return static_cast<int>(log(x)/log(base)); } int main() { int t,n; ll sol; int sieve[51] = {0}; vector<int> primes; for (int i = 2; i<=50;i++) { if (sieve[i] == 0) { primes.push_back(i); for (int j = i*i; j<=50; j+=i) { sieve[j] = 1; } } } cin >> t; while(t--) { cin >> n; sol = 1; for (vector<int>::iterator i = primes.begin(); i != primes.end(); ++i) { if (*i > n) {break;} sol *= pow(*i,logarithm(*i,n)); } cout << sol << endl; } }

flat20 + 0 comments I really like the computation of the power using logarithm. The observation is very easy to understand, yet I haven't thought of that.

I think the slowest part of the algorithm is the sieve construction so the complexity would be something like O(N * log(log(N))). In this part of your solution, I again found and interesting speed up by starting at i^2 in the inner circle which also makes sense but I always used naive start at i * 2 :)

ameyanator + 1 comment i tried your tip but am getting an error please help!

import java.io.*; import java.util.Arrays; class hackerrank { public static void main(String args[])throws IOException { System.out.println(""); BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); int t=Integer.parseInt(br.readLine()); for(int j=1;j<=t;j++) { int n=Integer.parseInt(br.readLine()); if(n%2==0) { Boolean a[]=new Boolean[n]; Arrays.fill(a,true); for(int i=2;i<Math.sqrt(n);i++) { if(a[i]==true) { int counter=0; for(int k=i*i;k<n;k=i*i+counter*i) { a[k]=false; counter++; } } } int ans=1; for(int i=2;i<n;i++) { int factor=1; if(a[i]==true) { int k=1; while(Math.pow(i,k)<=n) { factor=(int)Math.pow(i,k); k++; } } ans=ans*factor; } System.out.println(ans); } else { Boolean a[]=new Boolean[n+1]; Arrays.fill(a,true); for(int i=2;i<Math.sqrt(n);i++) { if(a[i]==true) { int counter=0; for(int k=i*i;k<n;k=i*i+counter*i) { a[k]=false; counter++; } } } int ans=1; for(int i=2;i<=n;i++) { int factor=1; if(a[i]==true) { int k=1; while(Math.pow(i,k)<=n) { factor=(int)Math.pow(i,k); k++; } } ans=ans*factor; } System.out.println(ans); } } } }

nafi_2018 + 0 comments You have done,but it looks like longest code try mine

[deleted] + 0 comments You can use euler003 to reverse engineer or verify the answer.

console.log(test_euler005(2520)) function test_euler005(n) { let factors = euler003(n) factors.shift() return factors } /** Modified euler003 to export all prime factors of N */ function euler003(n, divisor = 2, factors = []) { let square = (x) => Math.pow(x, 2) factors.push(divisor) while ((n % divisor) != 0 && square(divisor) <= n) { divisor++ } return square(divisor) <= n ? euler003(n / divisor, divisor, factors) : [...factors, n] }

rizky_eko_putra + 0 comments [deleted]vpinmrcool + 0 comments we have to find list of prime numbers for this. For this question you may hard code as max(N) = 40 but it will be costly operation to find as N grows.

juanfferrero6 + 0 comments Whats wrong?

ngopal253 + 0 comments so basically you are finding the LCM right?

shuklaaditya + 0 comments Nice observation. I solved it using euclidean gcd algorithm.

Rahul_zero + 2 comments For those getting stuck in test cases:

5342931457063200 5342931457063200 5342931457063200 5342931457063200 144403552893600 144403552893600 144403552893600 144403552893600 144403552893600 72201776446800 2329089562800 2329089562800 80313433200 80313433200 26771144400 26771144400 5354228880 5354228880 232792560 232792560 232792560 232792560 12252240 12252240 720720 360360 360360 360360 27720 27720 2520 2520 840 420 60 60 12 6 2

tenzin392 + 0 comments thanx buddy, I'm failing test cases #2 and #3 with a unique way of solving the problem. Now I'll test it with your help

merajmasuk + 0 comments [deleted]

richardpenman + 0 comments hmm, I used the brute force approach and passed all test cases. Maybe need to reduce the allowed time.

adityaishan27 + 3 comments we have to find the lcm as simple as that so for ..findind the lcm u just have to apply the algorithm of lcm=a*b/gcd(a,b)

mohitgupta_omg + 0 comments Thanks buddy..really simple and nice approach

mayankmangal2007 + 0 comments But this is not correct for more than 2 numbers.

harhacker + 0 comments [deleted]

chasezimmy + 1 comment **Python 2.7**Using reduce with lambda function to find LCM, I chose not to import gcd.def _gcd(x,y): while y!=0: x,y=y,x%y return x t = int(raw_input()) for _ in range(t): n = int(raw_input()) print reduce(lambda x,y: x*y/_gcd(x,y), range(1,n+1))

J___I + 0 comments Really nice solution! Using reduce to iteratively build up the LCM of {1,..,n} should have been obvious, but I wandered down a road of prime factorisations. Thanks for the post. My Python 3 solution on the same lines:

from math import gcd from functools import reduce for _ in range(int(input())): N = int(input()) print(reduce(lambda x,y: x*y//gcd(x,y), range(1,N+1)))

Sort 180 Discussions, By:

Please Login in order to post a comment