#はじめに
比較的大きな数（long型）で高速に素因数分解をしてみたくなったので、やってみました。

実行環境

cygwin 3.0.7-1
Surface Pro4

ソースコード

#include <stdio.h>
#include <math.h>
// #include <time.h>
#define A 1234567809876543 //素因数分解したい値を入力

long primeFactorization(long a){ //素因数分解を出力するプログラム
	long i,sq;
	if(a%2==0){ //偶数の場合
		printf("%ld\n",2);
		return primeFactorization(a/2); //2で割った値で再帰
	}
	sq = sqrt(a);
	for(i=3;i<=sq;i+=2){ //3以上√a以下の奇数の場合
		if(a%i==0){
			printf("%ld\n",i);
			return primeFactorization(a/i); //割れた値で再帰
		}
	}
	//偶数でも3以上√a以下の奇数の場合でも割り切れない場合
	if(a!=1){ //aが1でないなら、a自身は素数
		printf("%ld\n",a);	
	}
	return 0;
}

int main(){
	long a = A;
	// clock_t start,end;
	printf("%ld\n",a);
	// start = clock(); //実行時間計測開始
	primeFactorization(a);
	// end =clock(); //実行時間計測終了
	// printf("%.5f秒かかりました\n",(double)(end-start)/CLOCKS_PER_SEC);
	return 0;
}

注）時間計測に関わる行はコメントアウトしています。

実行結果

$ ./a.exe
1234567809876543
3
19
1439
15051483241
0.00000秒かかりました

参考サイト

素数判定高速化 | ユズノハのプログラミング学習サイト
https://programming-learning.com/2018/03/16/%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A-%E9%AB%98%E9%80%9F%E5%8C%96/