1602 - Hiperprimos

  • ID: 1602
  • IdBecrowd: 1602
  • Tags: matematica, programacao-dinamica
  • Nível: 8
  • Tempo Limite: 1 segundos
  • Memória: 200 MB
  • Categoria: Paradigmas
  • Autor: Marcio T. I. Oshiro

Descrição

Várias descobertas matemáticas da idade média são devidas a matemáticos árabes famosos como al-Khwarizmı 1 , Omar Khayyám, e Sharaf al-Dın al-Tusı entre outros. Um dos resultados pouco conhecido é sobre os números hiperprimos. Dizemos que um número é hiperprimo se ele tiver um número primo de divisores. Assim, por exemplo, 25 é hiperprimo, pois tem 3 divisores. Já 42 não é hiperprimo, pois tem 8 divisores.

Dado um inteiro N, determine o número de hiperprimos no intervalo [2, N].

Entrada

A entrada é composta por diversas instâncias e termina com final de arquivo (EOF).

Cada instância consiste de uma única linha contendo um único inteiro, N (2 ≤ N ≤ 2 × 10 6 ).

Saída

Para cada instância, imprima uma linha com a quantidade de hiperprimos no intervalo [2, N].

Exemplos

Exemplo de Entrada

2

                                4

Exemplo de Saída

1

                                3
Back to top