Prime conspiracy: Difference between revisions
no edit summary
No edit summary |
|||
Line 1,864:
Unfortunately, that prime number generator uses a table: while 1 million primes needs ~16MB*4|8, 10 million needs ~180MB*4|8, (both easily done on either 32 or 64 bit) 100 million would need ~2GB*8, (clearly 64 bit only) which is more than this 4GB box can allocate, it seems.
But it might work on a machine with lots more memory.
=={{header|Prolog}}==
While the program can handle a million primes, it's rather slow, so I've capped it to accept up to 100,000 primes.
<lang prolog>
% table of nth prime values (up to 100,000)
nthprime( 10, 29).
nthprime( 100, 541).
nthprime( 1000, 7919).
nthprime( 10000, 104729).
nthprime(100000, 1299709).
conspiracy(M) :-
N is 10**M,
nthprime(N, P),
sieve(P, Ps),
tally(Ps, Counts),
sort(Counts, Sorted), show(Sorted).
show(Results) :-
forall(
member(tr(D1, D2, Count), Results),
format("~d -> ~d: ~d~n", [D1, D2, Count])).
% count results
tally(L, R) :- tally(L, [], R).
tally([_], T, T) :- !.
tally([A|As], T0, R) :-
[B|_] = As,
Da is A mod 10, Db is B mod 10,
count(Da, Db, T0, T1),
tally(As, T1, R).
count(D1, D2, [], [tr(D1, D2, 1)]) :- !.
count(D1, D2, [tr(D1, D2, N)|Ts], [tr(D1, D2, Sn)|Ts]) :- succ(N, Sn), !.
count(D1, D2, [T|Ts], [T|Us]) :- count(D1, D2, Ts, Us).
% implement a prime sieve
sieve(Limit, Ps) :-
numlist(2, Limit, Ns),
sieve(Limit, Ns, Ps).
sieve(Limit, W, W) :- W = [P|_], P*P > Limit, !.
sieve(Limit, [P|Xs], [P|Ys]) :-
Q is P*P,
remove_multiples(P, Q, Xs, R),
sieve(Limit, R, Ys).
remove_multiples(_, _, [], []) :- !.
remove_multiples(N, M, [A|As], R) :-
A =:= M, !,
remove_multiples(N, M, As, R).
remove_multiples(N, M, [A|As], [A|R]) :-
A < M, !,
remove_multiples(N, M, As, R).
remove_multiples(N, M, L, R) :-
plus(M, N, M2),
remove_multiples(N, M2, L, R).
</lang>
{{Out}}
<pre>
?- conspiracy(4).
1 -> 1: 365
1 -> 3: 833
1 -> 7: 889
1 -> 9: 397
2 -> 3: 1
3 -> 1: 529
3 -> 3: 324
3 -> 5: 1
3 -> 7: 754
3 -> 9: 907
5 -> 7: 1
7 -> 1: 655
7 -> 3: 722
7 -> 7: 323
7 -> 9: 808
9 -> 1: 935
9 -> 3: 635
9 -> 7: 541
9 -> 9: 379
true.
</pre>
=={{header|Python}}==
| |||