素因数分解
この記事はリニューアルしました
https://ulprojectmail.blogspot.com/2021/11/n88-basicprime-2.html
N88-BASICで素数 (2回目)
素因数分解 (2回目 C)
N88-BASICで素数 (2回目)
(素因数分解 prime002.bas)
の速いほうのアルゴリズムをCで書きました
N88-BASICでは倍精度実数型を使用していましたが
Cでは整数の桁数がより多いunsigned long long型
(以後ULL型と記述します)を使用しています
使用したコンパイラでは
ルート(sqrt関数)がULL型に対応していないよう
でしたので、他方の2乗の比較で代用しました
その他、C用に多少の変更を加えてあります
実行速度が速すぎるため、より時間のかかる数値を
使用しました
446143574015233 = 127 524287 6700417
BASIC … 25 sec
C … 0.009 sec
で、約2778倍速でした
cl～.zip(prime002.c, prime002.exe, prime002.bas)
は以下のリンクからダウンロードできます
https://ulprojectmail.blogspot.com/p/n88-basicvl-basicnl-basic_20.html
Readme.txtを読んで遊んで下さい
prime002.c
/*
----------------------------------------------------------------------
Prime factorization by ULproject for C 2021.4
----------------------------------------------------------------------
*/
#include <stdio.h> /* printf,sscanf_s,gets_sを使うため */
#include <time.h> /* clock_t, clockを使うため */
/* このファイル内限定関数 */
static
void prime(unsigned long long n)
{ /* nの素因数分解 */
unsigned long long i, d;
printf("%llu = ", n);
i = 2;
d = 1;
while (i*i <= n)
{
if (n % i == 0)
{
printf(" %llu", i);
n /= i;
}
else
{
i += d;
d = 2;
}
}
printf(" %llu\n", n);
}
/* この関数から始まる(引数、戻り値なし) */
void main(void)
{
unsigned long long n;
clock_t t;
char buf[256];
for (;;)
{
printf("a～e or n≧2, n = ");
gets_s(buf, sizeof(buf)); /* 文字列入力 */
if (*buf == '\0') break; /* Enter終了 */
switch (*buf)
{
case 'a': n = 18446744073709551615ULL ; break;
case 'b': n = 127ULL * 524287ULL * 6700417ULL; break;
case 'c': n = 127ULL * 9007199254740997ULL ; break;
case 'd': n = 7ULL * 46116646144580591ULL ; break;
case 'e': n = 2ULL * 4611664614458057389ULL ; break;
default : sscanf_s(buf, "%llu", &n);
}
if (n < 2) break; /* 終了 */
t = clock();
prime(n);
t = clock() - t;
printf("%.3lf sec\n", (double)t / 1000.0);
}
}