首页 > 代码库 > Ugly Numbers
Ugly Numbers
Description
Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, ...
shows the first 10 ugly numbers. By convention, 1 is included.
Given the integer n,write a program to find and print the n‘th ugly number.
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, ...
shows the first 10 ugly numbers. By convention, 1 is included.
Given the integer n,write a program to find and print the n‘th ugly number.
Input
Each line of the input contains a postisive integer n (n <= 1500).Input is terminated by a line with n=0.
Output
For each line, output the n’th ugly number .:Don’t deal with the line with n=0.
Sample Input
1 2 9 0
Sample Output
1 2 10
刚开始这样做,为什么不对啊~
#include <iostream> #include <algorithm> #include <stdlib.h> using namespace std; int cmp(const void *a,const void *b) { return *(int *)a-*(int *)b; } int main() { int n; while(cin>>n&&n) { long int i,j,k,t=0,a[1505]; long int limit=100000000; for(i=1;i<limit;i=i*2) for(j=1;i*j<limit;j=j*3) for(k=1;i*j*k<limit;k=k*5) { a[t]=i*j*k; t++; } qsort(a,t,sizeof(int),cmp); cout<<a[n-1]<<endl; } return 0; }
#include<iostream> using namespace std; int main(void) { int n; while(cin>>n&&n) { int a[1505]={0}; int m2=0,m3=0,m5=0,i,t; a[0]=1; for(i=1;i<1500;i++) { if(2*a[m2]>3*a[m3]) t=a[m3]*3; else t=a[m2]*2; if(t>a[m5]*5) t=a[m5]*5; if(t == 2*a[m2]) m2++; if(t == 3*a[m3]) m3++; if(t == 5*a[m5]) m5++; a[i]=t; } cout<<a[n-1]<<endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。