SRM307 D2H PreprimeNumbers

TopCoder Statistics - Problem Statement

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

約数を$4$つ持つ数を$preprime$という．$1-indexed$で始めたと時，$n$番目の$preprime$はいくつか．

どの数も$1$と自身を約数に持つということで，$4$つの約数を持つということは$1$と自身以外に$2$つ持つということである．これは$2$つの素数の積(約数は$1, p, q, pq$)か，$1$つの素数の$3$乗の形(約数は$1, p, p ^2, p ^3$)になる．
$n \leq 10 ^6$ということで最大値はそこまで大きくないだろうと予想し，$10 ^7$を最大としてやった．エラトステネスの篩の要領で$2$から始めていき，その倍数のところをインクリメントしていく．予め$3$乗の数は$used$にメモしておく．オーバーフローに注意(落ちた)．

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <cmath>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair

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

int dp[10000000];
bool used[10000000];

class PreprimeNumbers {

    public:

    int nthNumber(int n) {
      ll i = 2;
      memset(dp, 0, sizeof(dp));
      memset(used, 0, sizeof(used));

      while(n) {
          if(dp[i] == 0 && i * i < 10000000 && i * i * i < 10000000) used[i * i * i] = true;
          if(dp[i] == 2 || used[i]) n--;

          for(ll j = i; j < 10000000; j += i) {
              dp[j]++;
          }
          i++;
      }

      return i - 1;
    }
};
Aug 28th, 2016
prime, srm, topcoder