tilper 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_ [deleted]
zerodivisible 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 Admin 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 please see why my code is wrong. sort discussion by recent
tenzin392 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 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 Why cant p^k be equal to N??
felix_m_roberts1 Perfectly possible, but doesn't change anything
sayamqazi a small change p^k <= N
dmitry_r 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 really a good idea
tilper No name as far as I know.
moremeds awesome!
sayamqazi It is called prime factorization. There exists only one unique prime factorization for any given number. See wikipedia "Prime factorization".
tilper 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 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 The statement I originally mentioned is most certainly not the Fundamental Theorem of Arithmetic, but it is slightly related.
AnastasiaP 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_arithmetic
That'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 wow, i have been banging my head in the wrong direction all along. Nice observation.
nikhil_nagaraju I thought of finding LCM for 1 to N numbers, but this is simpler.
Furcifer 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 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 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 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 You have done,but it looks like longest code try mine
[deleted] 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 [deleted]vpinmrcool 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 Whats wrong?
ngopal253 so basically you are finding the LCM right?
shuklaaditya Nice observation. I solved it using euclidean gcd algorithm.
Rahul_zero 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 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 [deleted]
richardpenman hmm, I used the brute force approach and passed all test cases. Maybe need to reduce the allowed time.
adityaishan27 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 Thanks buddy..really simple and nice approach
mayankmangal2007 But this is not correct for more than 2 numbers.
harhacker [deleted]
chasezimmy 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 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