如何判斷素?cái)?shù)
感謝你看到最后
題目要求:輸出100-200的素?cái)?shù)
首先我們要知道什么是素?cái)?shù)(質(zhì)數(shù)),以防有人忘記(比如剛學(xué)開(kāi)始學(xué)c的我就忘記了)
素?cái)?shù)(質(zhì)數(shù))只能被1和它自己整除
- 7只能被1和7整除,是素?cái)?shù)
- 9能被3整除,不是素?cái)?shù)
方法1—試除法
#include<stdio.h>
int main()
{
int i=0;
int count=0;
for(i=100;i<=200;i++)
{
int j=0;
for(j=2;j<i;j++)
{
if(i%j==0)//i可以整除j,i不是素?cái)?shù)
{
break;
}
}
if(j==i)//i只能整除它自己,是素?cái)?shù)
{
count++;
printf("%d ",i);
}
}
printf("
count=%d
",count);//計(jì)算100-200之間有幾個(gè)素?cái)?shù)
return 0;
}
這個(gè)代碼比較死,只是輸出了100到200之間的素?cái)?shù),完成了題目的要求
我們可以把它改造成輸入一個(gè)數(shù)字,判斷是否是素?cái)?shù)的形式
代碼改造1-1
- 用戶(hù)輸入一個(gè)數(shù)字
- 代碼判斷是否為素?cái)?shù)
- 是,輸出“是素?cái)?shù)”以及用戶(hù)輸入的值
- 不是,輸出“不是素?cái)?shù)”
#include<stdio.h>
int main()
{
int i=0;
int j=0;
scanf("%d",&i);
for(j=2;j<i;j++)
{
if(i%j==0)
{
printf("不是素?cái)?shù)
");
break;
}
}
if(j==i)
{
printf("是素?cái)?shù),i=%d
",i);
}
}
結(jié)果如下:
上面的這串代碼能很好地完成我們的需求,但它還有優(yōu)化的空間
方法2—開(kāi)平方法
方法1中的for循環(huán)為j<i
如果數(shù)字很大的話(huà),要循環(huán)非常多次才能出現(xiàn)j==i的情況
這就拖慢了我們程序運(yùn)行的速度
這里我們引入一個(gè)概念
- 若i=a*b
- a和b中至少有一個(gè)數(shù)字 <= 開(kāi)平方i
如16=2x8=4x4
其中2<4
這樣就能得到一個(gè)結(jié)論:
在根號(hào)i之前一定有一個(gè)數(shù)字n是非素?cái)?shù)的除數(shù)
如果找不到這個(gè)數(shù)字n,說(shuō)明該數(shù)字為質(zhì)數(shù)
利用開(kāi)平方法,我們可以將需要查找的數(shù)字范圍縮小很多
以下是用該方法完成開(kāi)頭題目要求的代碼示例
#include<stdio.h>
int main()
{
int i=0;
for(i=101;i<=200;i+=2)
{
int j=0;
for(j=2;j<=sqrt(i);j++)
{
if(i%j==0)
{
break;
}
}
if(j>sqrt(i))
{
printf("%d ",i);
}
}
return 0;
}
將這個(gè)代碼改造成1-1那種形式也不難,自己試試吧!
感謝你看到最后
如果這篇博客對(duì)你有幫助,請(qǐng)點(diǎn)贊支持一下,萬(wàn)分感謝!
本文摘自 :https://blog.51cto.com/u