# 【算法】普通方法和筛选法求素数

## 判断一个数是不是素数

``````//判断一个数是否为素数
bool isPlain(int value){
int m = sqrt(value);
if (value < 2) return false;
for (int i = 2; i <= m; i++){
if ((value%i)==0){
return false;
}
}
return true;
}``````

## 普通方法求解n以内的素数

``````//普通法求素数
bool* putong(int n){
bool* value = new bool[n];
for (int i = 0; i < n; i++)
value[i] = false;
for (int i = 2; i < n; i++){
if (isPlain(i)){
value[i] = true;
}
}
return value;
}``````

## 筛选法求n以内的素数

``````//筛选法求素数
bool* shuaixuan(int n){
bool* value = new bool[n];
for (int i = 0; i<n; i++)
value[i] = true;

value[0] = false;
value[1] = false;

for (int i = 2; i <= sqrt(n); i++){
if (value[i] && isPlain(i)){
int c = 2;
int j = i*c;
while (j < n){
value[j] = false;
j = i*c++;
}
}
}
return value;
}``````

## 完整代码及运行结果

``````#include <iostream>
using namespace std;
#include <ctime>
#include <math.h>
#include <conio.h>
//判断一个数是否为素数
bool isPlain(int value){
int m = sqrt(value);
if (value < 2) return false;
for (int i = 2; i <= m; i++){
if ((value%i)==0){
return false;
}
}
return true;
}

//普通法求素数
bool* putong(int n){
bool* value = new bool[n];
for (int i = 0; i < n; i++)
value[i] = false;
for (int i = 2; i < n; i++){
if (isPlain(i)){
value[i] = true;
}
}
return value;
}

//筛选法求素数
bool* shuaixuan(int n){
bool* value = new bool[n];
for (int i = 0; i<n; i++)
value[i] = true;

value[0] = false;
value[1] = false;

for (int i = 2; i <= sqrt(n); i++){
if (value[i] && isPlain(i)){
int c = 2;
int j = i*c;
while (j < n){
value[j] = false;
j = i*c++;
}
}
}
return value;
}

int main(){

int n;
while (cin >> n){

int start = clock();
bool* value1 = putong(n);
int end = clock();
cout << "普通方法：" << end - start << endl;

start = clock();
bool* value2 = shuaixuan(n);
end = clock();
cout << "筛选法：" << end - start << endl;

delete[] value1;
value1 = NULL;
delete[] value2;
value2 = NULL;
}
_getch();
}
``````

## hdu how many prime numbers 筛选法求素数

/* * hdu How many prime numbers * date 2014/5/13 * state AC */ #include <iostream> #include <cmath> #include <cstdio> using namespace std; bool isPrime(int x) { int sqr=sqrt(x*1.0); for(int i=2;i<=sqr;i++) { if(x%i==0)return false; }

## HDU 2136 Largest prime factor （筛选法求素数）

Largest prime factor Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 7297    Accepted Submission(s): 2589 Problem Description Everybody knows any number can be combined by the prime number. Now

## P168 筛选法求素数

#include <stdio.h>int main(){ int n,i,j,h=0; scanf("%d",&n); for(i=2;i<=n;i++) {  for(j=2;j<=i;j++)    {   if((i%j==0)&&(i!=j)) break;     else {printf("%d\n",i);break;} } }return 0;}

## hdu2824 The Euler function 筛选法求欧拉函数模板题

//求a , b范围内的所有的欧拉函数 //筛选法求欧拉函数模板题 #include<cstdio> #include<cstring> #include<iostream> using namespace std ; const int maxn = 3000010 ; typedef __int64 ll ; int e[maxn] ; int a ,  b ; void Euler() { int i,j; for (i=1;i<maxn;i++) e[i]