素因数分解

素因数分解

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