O objetivo é simples: calcule a função totiente para o maior número possível de números em 10 segundos e some os números.
Você deve imprimir o resultado no final e realmente calculá-lo. Nenhuma função automatizada de totiente é permitida, mas as bibliotecas de bignum são. Você precisa começar com 1 e contar todos os números consecutivos. Você não tem permissão para pular números.
Sua pontuação é quantos números seu programa pode calcular em sua máquina / quantos meu programa pode calcular em sua máquina . Meu código é um programa simples em C ++ (otimizações desativadas), espero que você possa executá-lo.
Propriedades importantes que você pode usar!
- E se
gcd(m,n) = 1, phi(mn) = phi(m) * phi(n)
- se
p
for primo,phi(p) = p - 1
(parap < 10^20
) - se
n
é par,phi(2n) = 2 phi(n)
- outros listados no primeiro link
Meu código
#include <iostream>
using namespace std;
int gcd(int a, int b)
{
while (b != 0)
{
int c = a % b;
a = b;
b = c;
}
return a;
}
int phi(int n)
{
int x = 0;
for (int i=1; i<=n; i++)
{
if (gcd(n, i) == 1)
x++;
}
return x;
}
int main()
{
unsigned int sum = 0;
for (int i=1; i<19000; i++) // Change this so it runs in 10 seconds
{
sum += phi(i);
}
cout << sum << endl;
return 0;
}
fastest-code
qwr
fonte
fonte
1, 3, 5, 2, 4
ou algo assim?Respostas:
Nimrod: ~ 38.667 (580.000.000 / 15.000)
Esta resposta usa uma abordagem bastante simples. O código emprega uma peneira simples de número primo que armazena o número primo da menor potência primária em cada slot para números compostos (zero para números primos), depois usa a programação dinâmica para construir a função totiente no mesmo intervalo e depois soma os resultados. O programa gasta praticamente todo o tempo construindo a peneira e calcula a função totiente em uma fração do tempo. Parece que tudo se resume à construção de uma peneira eficiente (com a leve torção de que também é preciso extrair um fator primo para números compostos do resultado e manter o uso da memória em um nível razoável).
Atualização: Desempenho aprimorado, reduzindo o consumo de memória e melhorando o comportamento do cache. É possível reduzir de 5% a 10% mais o desempenho, mas o aumento na complexidade do código não vale a pena. Por fim, esse algoritmo exercita principalmente o gargalo de von Neumann de uma CPU, e há muito poucos ajustes algorítmicos que podem contornar isso.
Também atualizou o divisor de desempenho, pois o código C ++ não era para ser compilado com todas as otimizações ativadas e mais ninguém o fazia. :)
Atualização 2: operação de peneira otimizada para melhor acesso à memória. Agora, manipule primos pequenos em massa via memcpy () (~ 5% de aceleração) e pule múltiplos de 2, 3 e 5 ao peneirar primos maiores (~ 10% de aceleração).
Código C ++: 9,9 segundos (com g ++ 4,9)
Código Nimrod: 9,9 segundos (com -d: release, backend do gcc 4.9)
fonte
Java, pontuação ~ 24.000 (360.000.000 / 15.000)
O código java abaixo faz o cálculo da função totiente e da peneira primária juntos. Observe que, dependendo da sua máquina, você precisa aumentar o tamanho inicial / máximo da pilha (no meu laptop bastante lento, eu tive que subir
-Xmx3g -Xms3g
).fonte
Nimrod: ~ 2.333.333 (42.000.000.000 / 18.000)
Isso usa uma abordagem totalmente diferente da minha resposta anterior. Veja os comentários para obter detalhes. O
longint
módulo pode ser encontrado aqui .fonte
2*sqrt(n)
), O que resulta em uma pontuação muito menor.C #: 49.000 (980.000.000 / 20.000)
/codegolf//a/26800 "Código de Howard".
Mas modificados, os valores phi são calculados para números inteiros ímpares.
Nova pontuação: 61.000 (1.220.000.000 / 20.000)
No "App.config", tive que adicionar "gcAllowVeryLargeObjects enabled = true".
fonte
Python 3: ~ 24.000 (335.000.000 / 14.000)
Minha versão é uma porta Python do algoritmo de Howard . Minha função original era uma modificação de um algoritmo introduzido neste post do blog .
Estou usando os módulos Numpy e Numba para acelerar o tempo de execução. Observe que normalmente você não precisa declarar os tipos de variáveis locais (ao usar o Numba), mas nesse caso eu queria reduzir o tempo de execução o máximo possível.
Editar: funções construtivas e resumidas combinadas em uma única função.
C ++: 9,99s (n = 14.000); Python 3: 9.94s (n = 335.000.000)
fonte
Aqui está minha implementação em Python que parece capaz de gerar ~ 60000 números em 10 segundos. Estou fatorando números usando o algoritmo pollard rho e usando o teste de primalidade de Rabin Miller.
fonte
φ (2 n ) = 2 n - 1
φ 2 (2 i ) = 2 i - 1 para i de 1 a n
Primeiro, algo para encontrar horários:
Para o código de referência, para mim, é:
Agora, Haskell:
Faz algo com 2525224 dígitos em 0,718 segundos. E agora estou apenas percebendo o comentário de @ Howard.
fonte
Matlab: 1464 = 26355867/18000
Como não posso testar seu código, dividi-o em 18000, pois representa o computador mais rápido daqueles que testaram. Eu vim para a pontuação usando esta propriedade:
Eu gosto principalmente que é um forro:
fonte
phi(p)
para todos os que não são primosp
?Python 2.7: 10.999 (165975/15090)
Pypy 2.3.1: 28.496 (430000/15090)
Alguns métodos interessantes que eu uso:
Teste de Pseudoprime Forte de Rabin-Miller - Um teste de primalidade que fornece um algoritmo probabilístico eficiente para determinar se um determinado número é primo
Fórmula do produto de Euler - O produto ultrapassa os números primos distintos que dividem n
Código:
fonte