素因数分解, エラトステネスの篩

#[レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】](https://qiita.com/e869120/items/eb50fdaece12be418faa#2-3-%E5%88%86%E9%87%8E%E5%88%A5%E5%88%9D%E4%B8%AD%E7%B4%9A%E8%80%85%E3%81%8C%E8%A7%A3%E3%81%8F%E3%81%B9%E3%81%8D%E9%81%8E%E5%8E%BB%E5%95%8F%E7%B2%BE%E9%81%B8-100-%E5%95%8F)

##前回の続き
[全探索：全列挙, 工夫して通り数を減らす全列挙, ビット全探索](https://qiita.com/RubyLrving/items/449048d8a8ce9ae14d7c)

##高速なべき乗計算
###[素因数分解](https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/1/NTL_1_A)

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<cctype>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {

    int n;
    cin >> n;

    cout << n << ':';
    int m=n, l=2;
    while(l*l<=m){
        if(m%l==0){
            cout << ' ' << l;
            m=m/l;
        }else{
            l++;
        }
    }
    if(m != 1) cout << ' ' << m;
    cout << endl;

    return 0;
}
```

###[D - 2017-like Number](https://atcoder.jp/contests/abc084/tasks/abc084_d)

単純に数値が素数か判定を行い入力値を処理するとTLEになります。
エラトステネスの篩というアルゴリズムを使い、１０００００までの数値が素数か判定します。
その後、累積和を使用し、一定区間のカウントを求めます。

```C++:C++
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;

bool is_prime_number[100001];
int dp[100002];

int main(int argc, const char * argv[]) {
    int q;
    cin >> q;

    is_prime_number[1]=true;
    for(int i=2; i<100001; i++){
        if(!is_prime_number[i]){
            for(int j=i+i; j<100001; j+=i){
                is_prime_number[j] = true;
            }
        }
    }

    for(int i=2; i<100002; i++){
        if(!is_prime_number[i] && !is_prime_number[(i+1)/2]){
            dp[i] = 1;
        }
    }

    for(int i=2; i<100001; i++){
            dp[i] += dp[i-1];
    }

    vector<int> l(q);
    vector<int> r(q);
    rep(i, q){
        cin >> l[i] >> r[i];
    }

    rep(i, q){
        cout << dp[r[i]] - dp[l[i]-1] << endl;
    }

    return 0;
}
```

###[A - 与えられた数より小さい素数の個数について](https://atcoder.jp/contests/tenka1-2012-qualC/tasks/tenka1_2012_9)

エラトステネスの篩というアルゴリズムを使い、１０００００までの数値が素数か判定します。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;
 
bool dp[100000];
 
int main() {
    int n;
    cin >> n;
 
    for(int i=2; i<n; i++){
        if(dp[i]) continue;
        for(int j=i+i; j<n; j+=i){
            dp[j] = true;
        }
    }
 
    int res=0;
    for(int i=2; i<n; i++){
        if(dp[i] == false) res++;
    }
    cout << res << endl;
    
    return 0;
}
```