URI/1602.cpp at master · joaoferrete/URI · GitHub

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
47
48
49
50
51
#include <bits/stdc++.h>

#define MAXN 2000001
using namespace std;

bitset<MAXN> prime;
int divr[MAXN], ans[MAXN];

void calc()
{
	prime.set();
	memset(divr, 0 , sizeof(divr));

	for (int i = 2; i < MAXN; i++)
	{
		if (prime[i])
		{
			divr[i] = 2;
			for (int j = i + i; j < MAXN; j+= i)
			{
				prime.reset(j);

				int divs = 0;
				int tam = j;

				while ( tam % i == 0) tam/= i, divs++;

				if (divr[j] == 0) divr[j] = divs + 1;
				else divr[j]*= (divs + 1);
			}
		}
	}

	ans[1] = 0;
	for (int i = 2; i <= MAXN; i++)
	{
		ans[i] = ans[i - 1];
		if (prime[divr[i]]) ans[i]++;
	}
}

int main()
{
	int n;

	calc();
	while(cin >> n)
	{
		cout << ans[n] << '\n';
	}
}