[easy] 263. Ugly Number不要用筛法做！

题目请戳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;
}