Para efeitos da nota atribuida à resolução de exercícios ao longo do semestre - Submeter até 23:59 de 13 de Março
(o problema continuará depois disponível para submissão, mas sem contar para a nota)
[para perceber o contexto do problema deve ler o guião da aula #02]
O Professor Pardal está fascinado com os números primos. Relembra que um primo é um número positivo maior que um que só é divisível por si próprio e por 1. Ele precisa da tua ajuda para saber quantos números primos existem num dado intervalo [A,B], ou seja, números primos maiores ou iguais a A e menores ou iguais a B. Será que podes ajudá-lo?
Nota que uma solução naive que passe por todos os números entre A e B e para cada um deles faça um ciclo para procurar os divisores não passa no tempo e precises de algo mais eficiente. A sugestão neste problema é que uses o Crivo de Eratóstenes.
Uma linha contendo dois inteiros A e B (2 ≤ A ≤ B ≤ 10 000 000).
Uma linha com um inteiro indicando a quantidade de números primos no intervalo [A,B].
| Input | Output |
|---|---|
2 100 |
25 |
| Input | Output |
|---|---|
123 4567 |
589 |
Estruturas de Dados (CC1007)
DCC/FCUP - Faculdade de Ciências da Universidade do Porto