Primos da forma 6x-1 até 1000 : [5, 11, 17, 23, 29, 41, 47, 53, 59, 71, 83, 89, 101, 107, 113, 131, 137, 149, 167, 173, 179, 191, 197, 227, 233, 239, 251, 257, 263, 269, 281, 293, 311, 317, 347, 353, 359, 383, 389, 401, 419, 431, 443, 449, 461, 467, 479, 491, 503, 509, 521, 557, 563, 569, 587, 593, 599, 617, 641, 647, 653, 659, 677, 683, 701, 719, 743, 761, 773, 797, 809, 821, 827, 839, 857, 863, 881, 887, 911, 929, 941, 947, 953, 971, 977, 983]
Compostos da forma 6x-1 até 1000 : [35, 65, 77, 95, 119, 125, 143, 155, 161, 185, 203, 209, 215, 221, 245, 275, 287, 299, 305, 323, 329, 335, 341, 365, 371, 377, 395, 407, 413, 425, 437, 455, 473, 485, 497, 515, 527, 533, 539, 545, 551, 575, 581, 605, 611, 623, 629, 635, 665, 671, 689, 695, 707, 713, 725, 731, 737, 749, 755, 767, 779, 785, 791, 803, 815, 833, 845, 851, 869, 875, 893, 899, 905, 917, 923, 935, 959, 965, 989, 995]
Tempo de execução: 0.000000 segundos (verificador teste 6x-1 primo ou nao primo)
ve se vc encontram algum erro… o tempo é bom medio , rapido para essa quantidade
o ruim é que tem que salvar todos
Compostos da forma 6x-1 até 100000 :
Tempo de execução: 0.031182 segundos
nao vou postar todos os numeros , so pra vê o tempo Primos da forma 6x-1 até 10000000 :
Compostos da forma 6x-1 até 10000000 :
Tempo de execução: 29.735742 segundos
Para saber se está certo ou não temos de saber o que pretendes. Parece-me, pelos números que mostras, que queres saber todos os números primos que obedecem à fórmula 6n-1. E queres saber se o teu cálculo para 10000000 em 29segundos é bom.
Em cima do joelho fiz um método que me dá o mesmo em menos de 2 segundos…
n: 1000 Primos: 86 Compostos: 80 Tempo: 13 ms
n: 100000 Primos: 4806 Compostos: 11860 Tempo: 8 ms
n: 10000000 Primos: 332383 Compostos: 1334283 Tempo: 1250 ms
… portanto 29 segundos está longe de ser bom.
Se mostrares o que tens, podemos guiar-te no caminho certo.
No seu caso específico, acho que dá pra otimizar um pouco. Em vez de testar um a um se é primo, é mais simples calcular apenas uma vez uma lista contendo todos os números primos até o valor limite. Está cheio de algoritmos assim por aí, exemplo.
Depois, basta ver quais números estão nesta lista pré-calculada:
import time
# adaptado de https://stackoverflow.com/q/4643647
def primesbelow(N):
#""" Input N>=6, Returns a list of primes, 2 <= p < N """
correction = N % 6 > 1
N = {0:N, 1:N-1, 2:N+4, 3:N+3, 4:N+2, 5:N+1}[N%6]
sieve = [True] * (N // 3)
sieve[0] = False
for i in range(int(N ** .5) // 3 + 1):
if sieve[i]:
k = (3 * i + 1) | 1
sieve[k*k // 3::2*k] = [False] * ((N//6 - (k*k)//6 - 1)//k + 1)
sieve[(k*k + 4*k - 2*k*(i%2)) // 3::2*k] = [False] * ((N // 6 - (k*k + 4*k - 2*k*(i%2))//6 - 1) // k + 1)
return [2, 3] + [(3 * i + 1) | 1 for i in range(1, N//3 - correction) if sieve[i]]
start = time.time()
limite = 10000000
smallprimeset = set(primesbelow(limite))
def isprime(n):
# http://en.wikipedia.org/wiki/Miller-Rabin_primality_test#Algorithm_and_running_time
if n % 2 == 0:
return False
return n in smallprimeset
compostos = []
primos = []
n = 5 # começa do 5 (valor de '6x - 1' quando x=1)
while n < limite:
if isprime(n):
primos.append(n)
else:
compostos.append(n)
n += 6 # soma 6 para encontrar o próximo número na forma 6x - 1
total = time.time() - start
Neste caso, eu gerei todos os primos menores que 10000000 e converti para um set, pois a busca em um set é mais rápido que em uma lista. Depois, para cada número, basta verificar se está no set para saber se é primo.
Vale lembrar que para medir tempos com mais precisão, recomenda-se usar o módulo timeit.
import time
def primos_e_compostos_6x_menos_1_ate(n):
inicio = time.time()
# Gera candidatos da forma 6x - 1 até n
candidatos = [6 * x - 1 for x in range(1, (n + 1) // 6 + 2) if 6 * x - 1 <= n]
compostos = set()
for p in candidatos:
if p in compostos:
continue
x = (p + 1) // 6
y = 1
while True:
composto = (6 * (x * (6 * y + 1) - y)) - 1
if composto > n:
break
compostos.add(composto)
y += 1
primos = [num for num in candidatos if num not in compostos]
compostos_finais = sorted(compostos.intersection(candidatos))
fim = time.time()
print(f"\n✅ Primos da forma 6x - 1 até {n}:")
print(primos)
print(f"\n❌ Compostos da forma 6x - 1 até {n}:")
print(compostos_finais)
print(f"\n⏱ Tempo de execução: {fim - inicio:.4f} segundos")
Exemplo de uso
limite = 10000000
primos_e_compostos_6x_menos_1_ate(limite) o codigo é esse postei errado , postei outro
10000000 1,5 segundo @pmlm @hugokotsubo
Primos da forma 6x - 1 até 10000000:
Compostos da forma 6x - 1 até 10000000:
Tempo de execução: 1.4733 segundos ok so para tester minha ideia . vi que nao é melhor… so para ter base perguntei .valeu. obrigado.
Dica: para formatar o código, basta selecioná-lo e usar o botão </> do editor:
Isso é mais importante ainda em Python, já que os espaços definem a identação, e sem formatar corretamente fica difícil pra quem quiser copiar o seu código e testar, por exemplo.
Outra alternativa é colocar o código entre ```, podendo inclusive informar a linguagem para que o highlight fique correto. Ou seja, isso:
```python
def f():
print('oi')
f()
```
É renderizado assim:
def f():
print('oi')
f()
import time
def primos_e_compostos_6x_menos_1_ate(n):
inicio = time.time()
# Gera candidatos da forma 6x - 1 até n
candidatos = [6 * x - 1 for x in range(1, (n + 1) // 6 + 2) if 6 * x - 1 <= n]
compostos = set()
for p in candidatos:
if p in compostos:
continue
x = (p + 1) // 6
y = 1
while True:
composto = (6 * (x * (6 * y + 1) - y)) - 1
if composto > n:
break
compostos.add(composto)
y += 1
primos = [num for num in candidatos if num not in compostos]
compostos_finais = sorted(compostos.intersection(candidatos))
fim = time.time()
print(f"\n✅ Primos da forma 6x - 1 até {n}:")
print(primos)
print(f"\n❌ Compostos da forma 6x - 1 até {n}:")
print(compostos_finais)
print(f"\n⏱ Tempo de execução: {fim - inicio:.4f} segundos")
# Exemplo de uso
limite = 1000000
primos_e_compostos_6x_menos_1_ate(limite)