### Prime number Ugly numbers are those number whose prime factors are 2, 3 or 5. Can you find out those ugly numbers? Specially 1 is considered as an ugly number

Input Format

The first line has a integer q. It is meaning there are q queries. Each query only contains a integer k.

Output Format

for each query, print the value of the k-th ugly number.

Sample Input 0

6
1
2
3
4
5
6
Sample Output 0

1
2
3
4
5
6

Below is my code, can only pass the sample test case, while the rests show wrong answers.

 ``12345678910111213141516171819202122`` `````` #include #include #include #include #include using namespace std; int main() { uint64_t Q; cin>>Q; while(Q--) { uint64_t k; cin>>k; if(k%2==0||k%3==0||k%5==0||k==1) cout< ``1234567891011121314151617181920212223242526272829303132333435363738394041`` ``````#include #include #include #include using namespace std; using INT = unsigned long long; //========================================================== vector ugly( INT N ) { vector result = { 1 }; set candidates{ 2, 3, 5 }; while ( result.size() < N ) { INT e = *candidates.begin(); candidates.erase( candidates.begin() ); if ( e > result.back() ) { result.push_back( e ); candidates.insert( 2 * e ); candidates.insert( 3 * e ); candidates.insert( 5 * e ); } } return result; } //========================================================== int main() { INT q; cin >> q; vector V( q ); for ( INT &e : V ) cin >> e; vector U = ugly( *max_element( V.begin(), V.end() ) ); for ( INT &e : V ) cout << U[e-1] << '\n'; }``````

Last edited on @lastchance, Try your code with these two inputs:

1
18446744073709551615 (max unsigned 64-bit value - 1)

10
11 12 13 14 15 16 17 18 19 20 @Pen72, Your code only checks if the number happens to have at least one factor of 2, 3, or 5, but in order to solve the problem it needs to check that the number ONLY contains those factors. So the naive implementation would be more like:

 ``123456789101112131415161718`` ``````#include using namespace std; int main() { int q; cin >> q; while (q--) { uint64_t n; cin >> n; auto m = n; while (m % 2 == 0) m /= 2; while (m % 3 == 0) m /= 3; while (m % 5 == 0) m /= 5; if (m == 1) cout << n << '\n'; } }``````

The naive implementation may be good enough for this problem since for 64-bit unsigned values there can only be a maximum of 63 factors of 2, 40 factors of 3, or 27 factors of 5.
Last edited on @DizzyDon,

 ```1 18446744073709551615 (max unsigned 64-bit value - 1)```

This example will overflow - but you've got to stop somewhere. Nothing is stated in the question about range. Actually, neither your nor my code will solve the original question for this input - see below.

Why do you imply that my code is wrong for the second example? I thought the queries were supposed to ask for the kth ugly number - NOT whether the input is or is not an ugly number. Neither your code nor the OP's flawed code reflect the question.

Original question:
 The first line has a integer q. It is meaning there are q queries. Each query only contains a integer k. For each query, print the value of the k-th ugly number.

For input
 ```10 11 12 13 14 15 16 17 18 19 20```

my code gives output
 ```15 16 18 20 24 25 27 30 32 36```

Since the ugly numbers (according to the definition given in the original post) are
 ```1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, .... ```

then:
the 11th ugly number is 15
the 12th ugly number is 16
the 13th ugly number is 18
etc.

This is what my code gives.

Last edited on  @lastchance, That makes more sense. I totally misunderstood the problem. you should be able to directly compute it.
the pattern is
a*2, a*3, a*5, (a+1)*2, (a+1)*3, ...
so the kth number is some mashup of k/3 and k%3.. right?

edit, its not a++ though, is it... that is what you were saying above.
its a = 2,3,5 cycled off previous values. Hmm.
Last edited on Thanks, I do understand the question now, why would I get some wrong answers using this code?
 ``123456789101112131415161718192021222324252627282930313233343536`` ``````#include #include #include #include #include #include using namespace std; void UglyNumber(uint64_t n) { vector A{1}; uint64_t a2=1,a3=1,a5=1,val; while(A.size()>Q; while(Q--) { cin>>k; UglyNumber(k);} return 0; }``````

Last edited on It won't work because your algorithm is wrong. Your numbers a2, a3 and a5 will have plenty of prime factors other than 2, 3 and 5.

No idea where you (mis)copied this from. ``1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768`` ``````#include #include #include #include int main() { // PRIME NUMBER VIA ERATOSTHENES SIEVE const int LIMIT{50}; std::vector numbers(LIMIT, 'P'); numbers = '-'; for(int j = 2; j < std::sqrt(LIMIT); j++) { for(int i = j * j; i < LIMIT; i+=j) numbers[i] = '-'; } // SIEVE AGAIN FOR UGLY NUMBERS int prime{0}; for(int j = 2; j < numbers.size(); j++) { if(numbers[j] == 'P') { prime = j; for(int i = prime; i < LIMIT; i += prime) { if( prime <= 5) numbers[i] = 'U'; else numbers[i] = '-'; } } } numbers = 'U'; // DISPLAY TYPE 1 - ALL UGLY's IN RANGE std::cout << "ALL UGLY NUMBERS IN RANGE:\n"; int count{0}; for(int i = 0; i < LIMIT; i++) { if(numbers[i] == 'U') { std::cout << std::setw(7) << std::right << i; count++; if(count % 12 == 0) std::cout << '\n'; } } std::cout << '\n'; // DISPLAY TYPE 2 - SELECT FOR AN UGLY int kth_ugly{0}; std::cout << "Enter k-th index: "; std::cin >> kth_ugly; count = 0; int index{0}; while( count < kth_ugly ) { if(numbers[index] == 'U') count++; index++; } std::cout << "Ugly number " << kth_ugly << " is " << index - 1 << '\n'; return 0; }``````
Last edited on
Topic archived. No new replies allowed.