Sequence number of the first n ugly, write code to run time is too long, want to know how to solve-CodePudding

Title description
If a number of factor contains only 2,3,5 or 7, so we call this number is called ugly, sequence 1,2,3,4,5,6,7,8,9,10,12,14,15,16,18,20,21,24,25,27... Shows the number of top 20 ugly,
Please programming to find the first n elements in the sequence,
Enter
Input contains multiple sets of test data, each group of input is an integer n (1 & lt;=n<=5842), when n=0, input end,
O
For each group of input, The output line "The NTH humble number is The number.", The inside of The n by The input of The value of n to replace, "st", "nd", "rd" and "th" The usage with reference to The sample output at The end of The ordinal number,
The sample input
1
2
3
4
11.
12
13
21
22
23
100
1000
5842
0
Sample output
The 1 st humble number is 1.
The 2 nd humble number is 2.
The 3 rd humble number is 3.
The 4 th humble number is 4.
The 11 th humble number is 12.
The 12 th humble number is 14.
The 13 th humble number is 15.
The 21 st humble number is 28.
The 22 nd humble number is 30.
The 23 rd humble number is 32.
The 100th humble number is 450.
The 1000th humble number is 385875.
The 5842 nd humble number is 2000000000.

Write the code

# include & lt; Iostream>
using namespace std;
Bool humble (int n);
Int main ()
{
Int I, j=0, k=0, count=0;
Int a, [10000].
Int s [10000];
for(i=0; I<=5842; I++)
{
Cin> A, [I].
If (a [I]==0)
break;
K++;
}
for(i=1; I<=2000000000; I++)
{
If (greet (I)==true)
{
S [j++]=I;
count++;
}
}
for(i=0; I{
If (j=a [I])
{
If (j % 10==1 & amp; & J % 100!=11)
Cout<" The "& lt; Else if (j % 10==2 & amp; & J % 100!=12)
Cout<" The "& lt; Else if (j % 10==3 & amp; & J % 100!=13)
Cout<" The "& lt; The else
Cout<" The "& lt; }
Cout<" The company number is "& lt; }
return 0;
}
Bool humble (int n)
{
Int I, j, num=0;
Int a, [10000].
Int b [10000];
Bool flag;
If (n==1)
Flag=1;
for(i=2; I * i<=n; I++)//QiuZhi factor
{
If I (n %==0)
A [num++]=I;
While (n % I==0)
N=n/I;
}
If (n> 1)
A [num++]=n;
For (j=0; J{
If (a [j]==2 | 3 | | a [j]==| a [j]==5 | | a [j]==7)
Flag=1;
The else
Flag=0;
}
return flag;
}
CodePudding user response:
Should be algorithm needs to be improved
CodePudding user response:
How do I look not to understand your topic.
If his prime factors are 2 hc-positie,
1 what is the prime factors of it?
CodePudding user response:
Divided by 2 in a row, until cannot be divided exactly by one step, the results to the above steps five,7,3 test, if the result is 1 is ugly, or not, if you can't be divided exactly by 2 hc-positie any are not
In addition, should build a table cache before calculated ugly for
CodePudding user response:
reference 3 floor early play play nuclear response:
divided by 2 in a row, until cannot be divided exactly by one step, the results to the above steps five,7,3 test, if the result is 1 is ugly, or not, if you can't be divided exactly by 2 hc-positie any are not
In addition, should build a table cache before calculated ugly for

A little problem, 22, can be divided exactly by 2, but not ugly,,,,
CodePudding user response:
references in 4th floor, the truth is more important than right or wrong response:

Quote: refer to the third floor early play big play nuclear war reply:

Divided by 2 in a row, until cannot be divided exactly by one step, the results to the above steps five,7,3 test, if the result is 1 is ugly, or not, if you can't be divided exactly by 2 hc-positie any are not
In addition, should build a table cache before calculated ugly for

A little problem, 22, can be divided exactly by 2, but not ugly,,,,

22 can be divided exactly by 2, 2/2=11, cannot be divided exactly by 2, then continue with 11 test 5,7,3, 11 are not divisible, the end result is
CodePudding user response:
Your algorithm efficiency is too low, a number of the prime factors are 2 hc-positie, you is to use this a few product of permutation and combination are good, don't a a loop judgment
For example, on the basis of the LZ to improve access to greet all collection

int s [5842];
Void greet ();
Int main ()
{
Int I, j=0, k=0;
Int a, [5842].
for(i=0; I<=5842; I++)
{
Cin> A, [I].
If (a [I]==0)
break;
K++;
}
The company ();

for(i=0; I{
J=a, [I].
If (j % 10==1 & amp; & J % 100!=11)
Cout<" The "& lt; Else if (j % 10==2 & amp; & J % 100!=12)
Cout<" The "& lt; Else if (j % 10==3 & amp; & J % 100!=13)
Cout<" The "& lt; The else
Cout<" The "& lt;
Cout<" The company number is "& lt; }
return 0;
}

Void greet ()
{
Int I, j, k, f=,1,1,1 {1} [], [] h=7,5,3,2} {, CNT=0;//s=2 in permutation and combination way ^ ^ 3 ^ n1 + n2 + 5 n3 + 7 ^ n4 interchange
bool flag=true;
While (flag)
{
K=f [1] [0] * f * f * f [3], [2]
If (k & gt; 0 & amp; & K & lt;
=2000000000){
S [cnt++]=k;
}
For (I=3; I>=0; I -)
{
K=1;
for (j=0; J{
K *=f [j];
}
If (f [I] <[I]=2000000000/h & amp; & [I] f * h [I] <=2000000000/k)
{
[I] f *=h [I];
break;
}
The else
{
F [I]=1;
If (I==0)
Flag=false;
}
}
}
for (i=1; I<5842; I++)//find the permutation and combination can be sorted after
{
for (j=0; J<5842 - I; J++)
{
If (s [j] & gt; S [m + 1])
{
K=s [j];
S [j]=s [j + 1);
S [m + 1]=k;
}
}
}
}
nullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnull