Tweakers dev challenge writeup - 11

Door Boudewijn op donderdag 1 oktober 2015 00:11 - Reacties (0)
Categorie: Tweakers dev challenge, Views: 850

Deze vond ik minder uitdagend, vooral omdat het standaardcode is.


De lijst getallen staat sowieso hier:
https://github.com/boudew...tweakers-challenge/11.txt


Wat ik als eerste gedaan heb is in de shell alvast optimaliseren door:

code:
1
johns-MacBook-Pro:tweakers-challenge john$ tr ' ' '\n' < 11.txt  | sort -u > 11.txt


Te draaien.
Dit levert 45595 hits in plaats va 54998 hits en alles staat meteen op een eigen regel en op volgorde. Altijd handig, maar uiteindelijk heb ik dat niet in de python code gebruikt.

De code in Python: https://github.com/boudew.../tweakers-challenge/11.py

Python:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import math

# het importeren van het bestand in een array...
lines=[]
with open('11.txt','r') as f:
    lines+= f.readlines()
    
input_getallen=[]
for i in lines:
    input_getallen+=map(lambda x: int(x), i.rstrip().split(" "))

# nu hebben we een list met de getallen uit de file.we sorteren die ook maar meteen.
input_getallen=sorted(input_getallen)

# we kunnen elk getal wel controleren op of het priem is, maar waarom niet alle priemgetallen tot het grootste getal uit de array nemen en die 2 sets over elkaar leggen?
#bron: http://stackoverflow.com/questions/21783160/sieve-of-atkin-implementation-in-python
def sieveOfAtkin(limit):
    P = [1,2,3]
    sieve=[False]*(limit+1)
    for x in range(1,int(math.sqrt(limit))+1):
        for y in range(1,int(math.sqrt(limit))+1):
            n = 4*x**2 + y**2
            if n<=limit and (n%12==1 or n%12==5) : sieve[n] = not sieve[n]
            n = 3*x**2+y**2
            if n<= limit and n%12==7 : sieve[n] = not sieve[n]
            n = 3*x**2 - y**2
            if x>y and n<=limit and n%12==11 : sieve[n] = not sieve[n]
    for x in range(5,int(math.sqrt(limit))):
        if sieve[x]:
            for y in range(x**2,limit+1,x**2):
                sieve[y] = False
    for p in range(5,limit):
        if sieve[p] : P.append(p)
    return P

# genereer alle priemgetallen tot het hoogste getal in. We maken er een set van omdat we zo een union operatie willen gebruiken 
priemgetallen=sorted(set(sieveOfAtkin(input_getallen[-1]+1)))

# deze filter en lambda voert in feite een intersectie in beide sets uit... items worden alleen bewaard indien ze in beide sets voorkomen
input_getallen=filter(lambda x: x in priemgetallen, input_getallen)
print (len(input_getallen))


Voor de priemgetal-test heb je een aantal welbekende functies, waaronder de zeef van Eratosthenes en het algoritme van Atkin. Die van Atkin is lekker snel en heb ik van internet gehaald.
ik heb voor Atikin gekozen omdat je makkelijk een limiet op kunt geven en dan gat het algoritme alle priemgetallen tot die limiet voor je genereren.

Omdat de getallen op regel 45 gesorteerd worden kan ik het laatste getal in de list als limiet voor atkin opgeven. Vervolgens le je de twee lijsten over elkaar en neem je alleen de getallen uit de vraagset die ook in de lijst met priemen voorkomen.

Verbeterpunt voor de volgende keer zou een set-union zijn wmb :).


Snel door naar: Boudewijns blog

Volgende: Tweakers dev challenge writeup - 12 10-'15 Tweakers dev challenge writeup - 12
Volgende: Tweakers dev challenge writeup - 10 10-'15 Tweakers dev challenge writeup - 10

Reacties

Er zijn nog geen reacties op deze post


Reactie formulier
(verplicht)
(verplicht, maar wordt niet getoond)
(optioneel)