読者です 読者をやめる 読者になる 読者になる

SRM442 Underprimes

概要
1と自分自身を除く素因数の数が素数となる値が A <= i <= B まででいくつ存在するか求めよ。

解法

#include <bits/stdc++.h>

using namespace std;

#define MAX (100001)

bool is_prime[MAX+10];

class Underprimes
{
public:
  
  void Sieve() {
    
    for(int i=0; i<=MAX; i++) {
      is_prime[i] = true;
    }
    
    is_prime[0] = is_prime[1] = false;
    
    for(long long i=2; i*i<=MAX; i++) {
      if(is_prime[i]) {
        for(long long j=i*i; j<=MAX; j+=i) {
          is_prime[j] = false;
        }
      }
    }
  }
  
  int countPrimeFact(int x) {
    
    int ret = 0;
    
    for(int i=2; i*i <= x; i++) {
      while(x % i == 0) {
        ret ++;
        x /= i;
      }
    }
    
    if(x!=1) ret++;
   	
    return ret;
  }
  
  int howMany(int l, int u) {
    
    Sieve();

    int ret = 0;
    
    for(int i=l; i<=u; i++) {
      ret += is_prime[countPrimeFact(i)];
    }
    
    return ret;
  }
};