题目请戳ugly Number
Write a program to check whether a given number is an ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5
. For example, 6, 8
are ugly while 14
is not ugly since it includes another prime factor 7
.
Note that 1
is typically treated as an ugly number.
正解
class Solution {
public:
bool isUgly(int num) {
while(num&&num%5==0) num/=5;
while(num&&num%3==0) num/=3;
while(num&&num%2==0) num/=2;
return num==1;
}
};
bool isPrime(int num)
{
if(num < 0) return false;
else if(num == 1) return false;
for(int i = 2;i<num;i++)
{
if(num%i == 0) return false;
}
return true;
}
素数筛法（没用）
#define Max 1000000
bool prime[Max>>1];
void IsPrime(){
memset(prime,true,sizeof(prime));
int n=Max>>1,m=(int)(sqrt(Max*1.0)/2.0);
for(int i=0;i<=m;i++)
if(prime[i])
for(int j=2*i*i+6*i+3;j<=n;j+=2*i+3)
prime[j]=false;
}
素数筛法（可以work）
#include<iostream>
using namespace std;
const long N = 200000;
long prime[N] = {0},num_prime = 0;
int isNotPrime[N] = {1, 1};
int main()
{
for(long i = 2 ; i < N ; i ++)
{
if(! isNotPrime[i])
prime[num_prime ++]=i;
//关键处1
for(long j = 0 ; j < num_prime && i * prime[j] < N ; j ++)
{
isNotPrime[i * prime[j]] = 1;
if( !(i % prime[j] ) ) //关键处2
break;
}
}
int num;
while(cin>>num)
{
cout<<isNotPrime[num]<<endl;
}
return 0;
}
