判断素数
素数即只能被1和其本身整除的数，判断n是否为素数只需用2~n/2或2~n之间的数去除就可以了，常用2~n/2，因为一个数的一半的平方大于其本身是从5开始的，解方程：n/2的平方>n 。即一个数n的两个因数不能同时比n/2大。就可以说一个数若不是素数则一定在2~n/2之间有因数。而且2，3也是符合下面程序的。
- 中文名 判断素数
- 外文名 To determine the prime numbers
- 又称 质数
- 特殊 1既不是素数，也不是合数。
基本概念
素数（又称质数）：
就是除了1和它本身，没有其他因子的整数。
注：1既不是素数，也不是合数。
简单算法
素数即只能被1和其本身整除的数，判断n是否为素数只需用2~n/2之间的数去除就可以了。因为一个数的一半的平方大于其本身是从5开始的，解方程：n/2的平方>n 。即一个数n的两个因数不能同时比n/2大。就可以说一个数若不是素数则一定在2~n/2之间有因数。而且2，3也是符合下面程序的。#include <stdio.h>
判断素数 main(){
int i,j,k=0;
for(i=2;i<=1000;i++)
{
for(j=2;j<=i/2;j++)
if(i%j==0)break;
if(j>i/2)
{
printf("%d ",i);
}
}}
判断算法
例如 17是素数，因为它不能被2~16间
任意一整数整除。因此判断一个整数m是否为素数，只需用2~m-1之间的每一个整数去除，如果都不能被整除，那么m就是一个素数。
其实可以简化，m不必被2~m-1之间的每一个整数去除，只需被2~根号m之间的每个数去除就可以了。例如判别17是否为素数，只需使2~4之间的每一个整数去除。为什么可以做如此简化呢？因为如果m能被2~m-1之间任意整数整除，如果这个数大于根号m，那这个数必定对应的还有一个比根号m小的因子（以16为例，2、8是它的因子，8大于4，2小于4）。
写了一个判断素数的函数，和大家分享。
//写一个能判断是否是素数的函数
#include <stdio.h>
#include <math.h>
#define TRUE 1
#define FALSE 0
void main(){
int n;
unsigned char judgePrime(int n);
printf("Input a number:n");
scanf("%d",&n);
if (judgePrime(n)==TRUE) {
printf("TRUEn");
}
else{
printf("FALSEn");
}
}
unsigned char judgePrime(int n){
int i;
unsigned char judge = TRUE;
if (n==2) {
judge = TRUE;
}
else if(n>2){
if (n%2==0) {
judge = FALSE;
}
else{
for (i=3;i<=sqrt(n);i+=2)
{
if (n%i==0)
{
judge = FALSE;
break;
}
}
}
}
else
{
judge = FALSE;
}
return judge;
}
简洁方法
bool prime(int n)
{
int a=2;
while (a<=n)
if (!(n%a++)) break;
if (a!=n) return 1;
return 0;
}
注:1. 返回值1,表示该数为素数.
2.该函数可在c和c++使用,bool为布尔顿型,也可以改为int型.
效率方法
#include<iostream>
#include<cmath>
using namespace std;
bool prime( int num)
{
if (num==2||num==3||num==5) return true;
unsigned long c=7;
if (num%2==0||num%3==0||num%5==0||num==1) return false;
int maxc=int(sqrt(num));
while (c<=maxc)
{
if (num%c==0) return false;
c+=4;
if (num%c==0) return false;
c+=2;
if (num%c==0) return false;
c+=4;
if (num%c==0) return false;
c+=2;
if (num%c==0) return false;
c+=4;
if (num%c==0) return false;
c+=6;
if (num%c==0) return false;
c+=2;
if (num%c==0) return false;
c+=6;
}
return true;
}
int main()
{
int num;
cin>>num;
if (prime(num)) cout<<num<<" is a prime number."<<endl;
else cout<<num<<" is not a prime number."<<endl;
return 0;
}
其他代码
代码一：
#include<iostream.h>
#include<math.h>
void zhishu(int n)
{
int i,s=1,t;
int w;
w=sqrt(n);//sqrt函数的函数头是math.h
for(i=2;i<=w;i++)
{
t=n%i;
if(t!=0)t=1;
s=s*t;
}
if(s)cout<<n<<'t';
}
void main(void)
{int k,j;
cin>>k;//输入2000，输出2000以内所有素数
for(j=2;j<=k;j++)
zhishu(j);
}
代码二：
#include<iostream>
#include<math.h>
using namespace std;
int main(void)
{
int isprimer(int num);
int x,point;
cout<<"Please enter a integer number(请输入一个正整数):"<<endl;
cin>>x;
point=isprimer(x);
if(point)
cout<<x<<" is a prime.("<<x<<"是素数)"<<endl;
else
cout<<x<<" is not a prime.("<<x<<"不是素数)"<<endl;
return 0;
}
int isprimer(int num)
{
int i,k;
k=sqrt(num);
for(i=2;i<=k;i++)
if(num%i==0)break;
if(i>=k+1&&num!=1)
return 1;
else
return 0;
}
90代码
判断依据：一个数N如果能被2～N/2之间的数整除，则该数不是质数；否则为质数。
Program Zhishu
Integer i,x,N,Sign
Read *,N
i=2
x=N/2
10 If(x<2) Then
Sign=1
Else If(x>=i.and.i>=2) Then
If(Mod(N,i).EQ.0) Then
Sign=0
Goto 20
Else
i=i+1
Goto 10
End If
Else If(i>x.and.x>=2) Then
Sign=1
End If
20 If(Sign==0) Print *,N,'不是素数'
If(Sign==1) Print *,N,'是素数'
End
算法介绍
using System;
using System.Collections.Generic;using System.Text;using System.Linq;protected internal int PrimeJudge(int zhengshu)//判断zhengshu是否是素数
{
if (zhengshu <= 1)
return -1;//不是大于1的整数,返回-1int sqOfzhengshu = (int)(Math.Sqrt(zhengshu));//zhengshu的平方根for (int i = 2; i <= sqOfzhengshu; i++)
{
if (zhengshu % i == 0)
return 0;//zhengshu是合数，返回0
}
return 1;//zhengshu是素数返回1
}