739(1): デフォルトの名無しさん [sage] 2023/06/09(金) 04:35:40.14 ID:Xuj67sW5(1) AAS
>>738
外部ﾘﾝｸ:ideone.com

力業っぽくなったな、3で割って1余る整数計しか解けない

742(2): デフォルトの名無しさん [] 2023/06/09(金) 20:08:26.01 ID:7Vf79qrZ(1) AAS
>>738 c
外部ﾘﾝｸ:ideone.com
#include <stdlib.h>
#include <math.h>
#include <stdio.h>
void sieve_of_eratosthenes(int n, int **isprime, int **primes_beg, int **primes_end) {
int i, m, j, nbytes = (1 + n) * sizeof **isprime, *map = malloc(nbytes), *beg = malloc(nbytes), *end;
for (i = 2; i <= n; i++) map[i] = 1;
for (i = 2, m = sqrt(n); i <= m; i++)
if (map[i]) for (j = i * i; j <= n; j += i) map[j] = 0;
for (i = 2, end = beg; i <= n; i++) if (map[i]) *end++ = i;
*isprime = map, *primes_beg = beg, *primes_end = end;
}
int main() {
int n = 1234567, *isprime, *primes_beg, *primes_end;
sieve_of_eratosthenes(n, &isprime, &primes_beg, &primes_end);

int *a, *b, c, count = 0;
for (a = primes_beg; a < primes_end && *a <= n / 3; a++)
for (b = a; b < primes_end && *b <= (c = n - *a - *b); b++)
if (isprime[c]) count++;
printf("count = %d\n", count);
return 0;
}

738(13): デフォルトの名無しさん [] 2023/06/08(木) 22:14:54.10 ID:B/+C/EDE(2/2) AAS
お題：1234567以下の素数 a, b, c で a + b + c = 1234567 かつ a ≤ b ≤ c を満たす組み合わせは何通りあるか計算せよ。

761(6): 638 [sage] 2023/06/11(日) 02:58:42.46 ID:aJTqIDxz(1/2) AAS
力ずく問題は苦手なインタプリタ―だが、速度に配慮した書き方をすればこの規模だと数分程度で解ける…

use feature qw{:5.16 signatures say};
$m = 1234567;
%h = map{$_ => ++$k} 2..$m;
for $i (2..int(sqrt $m)) {
　if (exists $h{$i}) {
　　for ($i..(int($m / $i)+1)) { delete $h{$i * $_} }
　}
}
@p = sort{$a <=> $b} keys %h;
%o = map{$p[$_] => $_} 0..$#p;
for $i (0..$#p-2) {
　$p1 = $p[$i];
　last if $m <= 3 * $p1;
　for $j ($i+1..$#p-1) {
　　$p2 = $p[$j]; $s = $p1 + $p2;
　　$r = $m - $s; last if $r <= $p2;
　　$n++ if exists $o{$r};
　}
}
print "n = $n\n";

実行結果 (CPUは Core-i7 8995u、Mem: 32GB)
$ time perl 21_738_prime+1234567.pl
n = 151055501

real 5m48.035s
user 5m44.468s
sys 0m3.250s

出題者の解と合わん…＞＜

785(2): デフォルトの名無しさん [sage] 2023/06/15(木) 22:01:30.16 ID:4JYva2qR(1/2) AAS
fftなんぞ使って早くなんかならんというに
原理わかってんの？
例えばHaskellの標準のinteger型は何万桁でも計算できる、その際fftで掛け算するので数万桁まで行ってもそこそこ早い
しかし逆に32bitで収まるような計算だと遅くなる
だから“この計算はfftなんか使わなくていいよ、int32の範囲で収まるからそれで計算してね”と専用の型がいっぱいある
Rがそれで早くなるなら素の標準計算がしょぼいとかインタプリタ特有の話
そもそも計算速度気にする場合にRを選択してる時点で筋違い