素数判定

• 「２からｎ−１までの整数で割り算して、その何れでも割り切れないならば素数である」ということを利用したプログラムです。

  /*キーボードから入力した２以上の自然数が素数かどうかを判定し表示する*/
  #include <stdio.h>
  
  main()
  {
  	int	n;	/* 入力数 */
  	int	k;	/* 割る数 */
  
  	printf("２以上の自然数を入力して下さい：");
  	scanf("%d", &n );
  	for( k = 2; k < n; k++ )
  	{
  		if( n%k == 0 )
  		{
  			printf("%d は合成数です\n", n );
  			return;/* 関数から出て行く */
  		}
  	}
  	printf("%d は素数です\n", n );
  }
  /* end of prime.c */
  

• このプログラムでは、２からｎ−１までの全ての整数を因数候補として調べてしまっています

　無駄な割り算の回数を減らす工夫せよ。

1. 例えば４９＝７×７であるから、与えられた数の平方根までの因数候補について調べれば良い
   ヒント：double sqrt(double x)
   
   
2. ２より大きい素数は奇数であることを利用せよ
   ヒント：３以上については奇数のみを因数候補とすれば良い

素因数分解

最大公約数