所謂素數是指除了1和它本身以外,不能被任何整數整除的數,例如17就是素數,因為它不能被2~16的任一整數整除。因此判斷一個整數m是否是素數,只需把m被2~m-1之間的每一個整數去除,如果都不能被整除,那麼m就是一個素數另外判斷方法還可以簡化。m不必唄2~m-1之間的每一個整數去除,只需被2~√m之間 ...
所謂素數是指除了1和它本身以外,不能被任何整數整除的數,例如17就是素數,因為它不能被2~16的任一整數整除。因此判斷一個整數m是否是素數,只需把m被2~m-1之間的每一個整數去除,如果都不能被整除,那麼m就是一個素數
另外判斷方法還可以簡化。m不必唄2~m-1之間的每一個整數去除,只需被2~√m之間的每一個整數去除就可以了。如果m不能被2~√m間任一整數整除,m必定是素數。例如判別17是是否為素數,只需使17被2~4之間的每一個整數去除,由於都不能整除,可以判定17是素數。(原因:因為如果m能被2~m-1之間任一整數整除,其二個因數必定有一個小於或等於√m,另一個大於或等於√m。例如16能被2,4,8整除,16=2*8,2小於4,8大於4,16=4*4,4=√16,因此只需判定在2~4之間有無因數即可)
#include<stdio.h>
#include<math.h>
void main()
{
int m,i,k;
printf("請輸入一個整數:");
scanf("%d",&m);
k=(int)sqrt(m);
for(i=2;i<=k;i++)
if(m%i==0)
break;
if(i>k)
printf("%d 是素數。\n",m);
else
printf("%d 不是素數。\n",m);
}