C++

Forum

 
Prime number

Pen72 (74)
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
  #include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
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<<k<<"\n";
    }

    return 0;
}
lastchance (6980)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
 
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

using INT = unsigned long long;

//==========================================================

vector<INT> ugly( INT N )
{
   vector<INT> result = { 1 };
   set<INT> 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<INT> V( q );
   for ( INT &e : V ) cin >> e;
   
   vector<INT> U = ugly( *max_element( V.begin(), V.end() ) );
   for ( INT &e : V ) cout << U[e-1] << '\n';
}


Last edited on
DizzyDon (121)
@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
DizzyDon (121)
@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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
#include <iostream>
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
lastchance (6980)
@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
againtry (2313)
DizzyDon (121)
@lastchance, That makes more sense. I totally misunderstood the problem.
jonnin (11437)
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
Pen72 (74)
Thanks, I do understand the question now, why would I get some wrong answers using this code?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
 
void UglyNumber(uint64_t n)
{
        vector<uint64_t> A{1};
        uint64_t a2=1,a3=1,a5=1,val;
        while(A.size()<n)
        {
            val=min(a2*2,min(a3*3,a5*5));
            if(val==a2*2)
                    a2++;
            else if(val==a3*3)
                    a3++;
            else 
             a5++;
           A.push_back(val);
        }
        
      
        cout<<A[n - 1]<<"\n";
}

int main() {
    uint64_t  Q,k;
    cin>>Q;
    while(Q--)
    { cin>>k;
    UglyNumber(k);}
    return 0;
}

Last edited on
lastchance (6980)
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.
againtry (2313)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
 
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

int main()
{
    // PRIME NUMBER VIA ERATOSTHENES SIEVE
    const int LIMIT{50};
    std::vector<char> numbers(LIMIT, 'P');
    numbers[0] = '-';
    
    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[1] = '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.