素因数分解

この記事はリニューアルしました
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);
}
}