1602-hiperprimos

# yaml-language-server: $schema=https://api.mundodocodigo.com.br/api/public/json/wok-problem.json --- version: "0.5" id: 1602 name: "Hiperprimos" slug: "hiperprimos" timelimit: 1.0 memlimit: 200 difficultyLevelId: D author: "Marcio T. I. Oshiro" origin: "Beecrowd" description: 'Cálculo linear de Números Hiperprimos utilizando o Crivo de Eratóstenes na Divisão.' editorial: | A solução requer precomputar o número de divisores e verificar se ele é primo. A forma mais rápida é usar o Crivo para contar divisores ou perceber que só números na forma p^(q-1) (onde p e q são primos) têm q divisores. Entretanto, como N é pequeno (2*10^6), um Crivo em O(N log N) que soma +1 aos seus múltiplos resolve instantaneamente o problema! Outra abordagem ainda mais rápida é rastrear o Menor Fator Primo (SPF) de 1 até N. successmsg: 'Parabéns! Encontrar divisores de maneira pré-computada mostra sua evolução em teoria dos números.' timeComplexity: O(N log N) skills: - primes-sieve - number-theory statements: - id: a-hiperprimos testScenarioLevel: A thematicSkills: - skill: number-theory points: 2 - skill: primes-sieve points: 1 testScenarios: - id: a-performance name: Limites Máximos description: "Milhões de consultas para teste de O(N log N) ou O(N)" helpTip: "Sua solução falhou no limite. Pré-calcule as respostas até N!" level: A testType: PERFORMANCE skills: - skill: primes-sieve points: 1 - id: b-fuzzing name: Casos Variados description: "Múltiplos testes." helpTip: "A inicialização foi feita corretamente para múltiplos casos de teste?" level: B testType: TDD skills: - skill: basic-io points: 1 - id: c-edge name: Limites Iniciais description: "Testando com os menores N, como 2, 3 e 4." helpTip: "O menor Hiperprimo é 2!" level: C testType: TDD skills: - skill: logic points: 1 - id: d-sample name: Exemplo description: "Exemplo base." helpTip: "Passe." level: D testType: TDD skills: - skill: logic points: 1 solutions: - id: a-otima-basica name: Crivo SPF / Contagem Prefix description: O(N log N) Crivo adaptado para Divisores e Soma de Prefixos. level: A implementations: - language: cpp paradigm: Imperative main: hiperprimos.cpp filenames: - hiperprimos.cpp - language: py paradigm: Imperative main: hiperprimos.py filenames: - hiperprimos.py - language: java paradigm: OO main: Hiperprimos filenames: - Hiperprimos.java authorSlugProblem: Unknown defaultStatement: a-hiperprimos