Матч 307, Препростое число (PreprimeNumbers)

Дивизион 2, Уровень 3

Число называется препростым, если оно имеет в точности 4 делителя. Например, 6 является препростым, так как оно имеет 4 делителя: 1, 2, 3 и 6. Последовательность препростых чисел имеет вид: 6, 8, 10, 14, … . Найти n - ое препростое число (индексирование n начинается с 1).

Класс: PreprimeNumbers

Метод: int nthNumber(int n)

Ограничения: 0 £ n £ 1000000.

Вход. Натуральное число n.

Выход. n - ое препростое число.

Пример входа

n

2

4

24

Пример выхода

8

14

77

РЕШЕНИЕ

простые числа

Число является препростым тогда и только тогда, когда оно является либо произведением двух простых, либо третьей степенью некоторого простого числа. При помощи решета Эратосфена строим массив primes, для которого primes[i] = 1 тогда и только тогда, когда i является простым. Заносим в массив res препростые числа. Сортируем массив res и возвращаем n - ое число. Поскольку res[0] содержит первое препростое число, то n - ое препростое число находится в res[n – 1].

ПРОГРАММА

#include <cstdio>

#include <algorithm>

#define MAX 6000001

using namespace std;

int primes[MAX], res[MAX], ptr = 0;

void gen_primes()

{

int i, j;

for(i = 0; i < MAX; i++) primes[i] = 1;

for(i = 2; i * i <= MAX;i++)

if (primes[i])

for(j = i; j * i < MAX; j++) primes[i * j] = 0;

}

class PreprimeNumbers

{

public:

int nthNumber(int n)

{

int i, j;

gen_primes();

for(i = 2; i < MAX; i++)

{

if (i * (i + 1) > MAX) break;

if (primes[i])

for(j = i + 1; j < MAX; j++)

{

if (i * j > MAX) break;

if (primes[j]) res[ptr++] = i * j;

}

}

for(i = 2; i * i * i < MAX; i++)

if (primes[i]) res[ptr++] = i * i * i;

sort(res,res+ptr);

return res[n-1];

}

};