• 埃拉托色尼筛选法
埃拉托色尼筛选法

简介

针对自然数列中的自然数而实施的，用于求一定范围内的质数。

算法思想

挖去1;
用刚才被挖去的数的下一个数p，把p的倍数挖掉;
检查p是否小于sprt(n)的整数部分，如果是，则返回(2)继续执行，否则就结束;
纸上剩下的数就是素数。
代码

递归实现

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int* Get_Prime(int num)
{
int *a = NULL, *get = NULL;
int *p = NULL, *q = NULL;
int i = 0, j = 0;

/*
*  the exit.
*/
if (num <= 10)
{
a = malloc (sizeof(int) * 10);

for (i = 0; i < 10; i++)
a[i] = 0;

a[2-1] = 2; a[3-1] = 3;
a[5-1] = 5; a[7-1] = 7;

a[num - 1] = -1;

return a;
}

/*
*  step 1: get the prime under sqrt(num)
*/
get = Get_Prime ((int)( sqrt ((double)num) + 0.5 ));

/*
*  step 2: malloc the space of 1 - num.
*/
a = malloc (sizeof(int) * (num));

/*
* step 3: init the space.
* The end is -1 as a sign.And take out number 1;
*/
for (i = 0; i < num; i++)
a[i] = i + 1;
a[num - 1] = -1;    a[0] = 0;

/*
* step 4: take out the number n*(*p)
*/
for (p = get; (*p) != -1; p++)
{
if (*p == 0)
continue;

for (j = 2; (*p) * j < num; j++)
a[ (*p) * j - 1] = 0;//printf("take out%d, in %d,at %d\n",(*p)*j,*p,num);
}

/*
* step 5:return and free
*/
free (get);
return a;
}

int main()
{
int num;
int *a = NULL;
int i;

scanf ("%d", &num);

if (num <= 0)
return 0;

a = Get_Prime (num);

for (i = 0; a[i] != -1; i++)
if (a[i])
printf ("%d ", a[i]);

putchar('\n');

return 0;
}

循环实现

#include "stdio.h"
#include "math.h"

int isPrime(int n)
{
int sqt = sqrt((double)n);
int i;

for(i = 2; i <= sqt; i++  )
{
if(n%i==0) return 0;
}
return 1;
}

void GetPrime_Erato(int *n)
{
int *num = NULL, *num_sqrt = NULL;
int *q = NULL, i = 0, *p = NULL;
int sqr = (int)sqrt((double)*n);

//¥¥Ω®ƒ⁄¥Êø’º‰
num = (int *) malloc(sizeof(int)*(*n));
if(!num)
{
printf("ƒ⁄¥Ê≤ª◊„£°");
exit(1);
}

num_sqrt = (int *) malloc(sqr * sizeof(int)) ;
if(!num_sqrt)
{
printf("ƒ⁄¥Ê≤ª◊„£°");
exit(1);
}

//ƒ⁄¥Êø’º‰≥ı ºªØ
for(i = 0; i <  (*n); i++)
num[i] = i + 1;
for(i = 0; i < sqr; i++)
num_sqrt[i] = i + 1;

//‘≠ º ‰≥ˆ
printf("\n");
printf("%d“ªœ¬µƒ ˝”–:", *n);
for(q = num; q < &num[(int)(*n)] ; q++)
{
if(*q != 1)
printf("%d\t", *q);
}
printf("\n");
printf("\n");

//…æ≥˝
for(q = &num_sqrt[1]; q < &num_sqrt[sqr]; q++)
{
if(isPrime(*q))
{
for(i = *q + 1; i <= *n; i++)
{
if(i % *q == 0)
num[i-1] = 1;
}

printf("…æ≥˝ %d µƒ±∂ ˝∫Û:", *q);
for(p = num; p < &num[*n] ; p++)
{
if(*p != 1)
printf("%d\t", *p);
}
printf("\n");
}
}

// ‰≥ˆ
printf("\n");
printf("%d“ªœ¬µƒÀÿ ˝”–:", *n);
for(q = num; q < &num[(int)(*n)] ; q++)
{
if(*q != 1)
printf("%d\t", *q);
}

}

int main()
{
int n = 100;

GetPrime_Erato(&n);

return 0;
} 

说明

递归实现的编写时间是2017年，循环实现是在2015年，其中由于平台的原因，中文字体在Mac上是无法识别的所以产生了乱码。
展开全文
• 埃拉托色尼筛选法埃拉托色尼筛选法概念步骤优化代码 埃拉托色尼筛选法 概念 埃拉托色尼筛选法(the Sieve of Eratosthenes)简称埃氏筛法，是古希腊数学家埃拉托色尼提出的一种筛选法 作用： 产生一个不大于给定整数n...
埃拉托色尼筛选法埃拉托色尼筛选法概念步骤优化代码
埃拉托色尼筛选法
概念
埃拉托色尼筛选法(the Sieve of Eratosthenes)简称埃氏筛法，是古希腊数学家埃拉托色尼提出的一种筛选法
作用：
产生一个不大于给定整数n的连续质数序列
（质数是大于 1 并且只有 1 和 这个素数本身作为因数（因子） 的正整数。）
步骤

初始化一个2~n的连续整数序列，作为候选质数（1只有它自己本身这一个因数。所以1既不是质数,又不是合数）
找到当前最小的数2，消去2的倍数，例如4，6，8等
再指向下一个最小的数3，消去3的倍数，例如6，9，12等
再指向下一个最小的数5，消去5的倍数，例如10，15，20等
.
.
.
该算法 以这个方式不断的做下去直到序列中已经没有可以消去的元素为止，剩下的就是我们要求的质数

优化

根据上面的步骤我们发现有很多数字被重复消去，比如6被消去了两次
消去x的倍数时，$x^2$不会大于n，p也不会大于$\sqrt[]{n}$的向下取整的值（$\lfloor$ $\sqrt[]{n}$$\rfloor$，向下取整函数）以$x^2$ $\le$ n作为判断循环的条件

代码
public int[] Sieve(int n) {
int[] A = new int[n+1];
for (int i = 2; i <= n; i++) {
A[i] = i;
}
for (int i = 2; i <= Math.floor(n); i++) {
if (A[i] != 0) {//没有被前面消除
int j = i * i;
while (j <= n) {
A[j] = 0;//标记已经删除
j = j + i;
}
}
}
int s=0;
int[] L = new int[n+1];
for (int i = 2; i <= n; i++) {
if (A[i] != 0) {
L[s] = A[i];
s = s + 1;
}
}
return L;
}



展开全文
• ## Java实现埃拉托色尼筛选法

万次阅读 多人点赞 2019-07-20 21:43:16
翻译：使用埃拉托色尼筛选法计算两个整数的最大公约数。（PS：最大公约数也称最大公因数，指两个或多个整数共有约数中最大的一个） 2 解决方案 2.1 埃拉托色尼筛选法原理简介 引用自百度百科： 埃拉托色尼筛选法(the...
1 问题描述
Compute the Greatest Common Divisor of Two Integers using Sieve of Eratosthenes.
翻译：使用埃拉托色尼筛选法计算两个整数的最大公约数。（PS：最大公约数也称最大公因数，指两个或多个整数共有约数中最大的一个）
2 解决方案
2.1 埃拉托色尼筛选法原理简介
引用自百度百科：
埃拉托色尼筛选法(the Sieve of Eratosthenes)简称埃氏筛法，是古希腊数学家埃拉托色尼(Eratosthenes 274B.C.～194B.C.)提出的一种筛选法。 是针对自然数列中的自然数而实施的，用于求一定范围内的质数，它的容斥原理之完备性条件是p=H~。
具体求取质数的思想：
（1）先把1删除（现今数学界1既不是质数也不是合数）
（2）读取队列中当前最小的数2，然后把2的倍数删去
（3）读取队列中当前最小的数3，然后把3的倍数删去
（4）读取队列中当前最小的数5，然后把5的倍数删去
（5）如上所述直到需求的范围内所有的数均删除或读取
下面看一下执行上述步骤求不大于100的所有质数的一个示意图：

2.2 具体编码
本文求取两个数的最大公约数，采用质因数分解法：把每个数分别分解质因数，再把各数中的全部公有质因数提取出来连乘，所得的积就是这几个数的最大公约数。
例如：求24和60的最大公约数，先分解质因数，得24=2×2×2×3，60=2×2×3×5，24与60的全部公有的质因数是2、2、3，它们的积是2×2×3=12，所以，（24，60）=12。
此处，第一步，先使用埃拉托色尼筛选法求取不大于数A的所有质数，然后从这些质数中选取A的所有质因数；第二步，依照第一步思想求取数B的所有质因数；第三步，求取数A和数B公共质因数；第四步，输出数A和数B的最大公约数。
具体代码如下：
package com.liuzhen.ex1;

import java.util.Scanner;

public class SieveOfEratosthenes {
//返回一维数组，数组中的元素为不大于n的所有质数
public static int[] getPrime(int n){
int[] result1 = new int[n];   //定义一个一维数组，并从第2个元素依次初始化为相应的自然数
for(int i = 2;i < n+1;i++){
result1[i-1] = i;
}
for(int i = 2;i < n;i++){
for(int j = i+1;j < n+1;j++){
if(j % i == 0)          //如果j能够整除i，使result[j-1]等于0
result1[j-1] = 0;
}
}
int[] result2 = getNoneZero(result1);  //除去result数组中所有0元素
return result2;     //数组中非零元素即为不大于n的所有质数
}

//返回一维数组，该数组的元素为参数数组中所有不为0的元素值
public static int[] getNoneZero(int[] A){
int len = 0;
for(int i = 0;i < A.length;i++){
if(A[i] != 0)
len = len+1;
}
int[] result = new int[len];
int k = 0;
for(int i = 0;i < A.length;i++){
if(A[i] != 0){
result[k] = A[i];
k++;
}
}
return result;
}

//求取一个数n的所有质因数(eg:24=2×2×2×3,则result[] = {2,2,2,3})
public static int[] getNprime(int n){
int[] primes = getPrime(n);
int[] result;        //最终返回结果集
int len = 0;         //返回结果集数组长度，初始化为0
for(int i = 0;i < primes.length;i++){
int temp = n;
while(temp % primes[i] == 0){
temp = temp/primes[i];
len++;
}
}
result = new int[len];
int k = 0;
for(int i = 0;i < primes.length;i++){
int temp = n;
while(temp % primes[i] == 0){
temp = temp/primes[i];
result[k] = primes[i];
k++;
}
}
return result;
}

//返回两个一维数组中所有共同元素
public static int[] getCommonPrime(int[] A , int[] B){
int[] result;
int lenA = A.length;
int lenB = B.length;
if(lenA < lenB){
result = new int[lenA];
for(int i = 0;i < lenA;i++){
int temp = A[i];
for(int j = 0;j < lenB;j++){
if(temp == B[j]){
result[i] = A[i];
B[j] = 0;
break;
}
}
}
}
else{
result = new int[lenB];
for(int i = 0;i < lenB;i++){
int temp = B[i];
for(int j = 0;j < lenA;j++){
if(temp == A[j]){
result[i] = B[i];
A[j] = 0;
break;
}
}
}
}
int[] result1 = getNoneZero(result);
return result1;
}

//求取数A和B的最大公约数
public static void getMaxCommonDivisor(int A,int B){
int[] primesA =  getNprime(A);  //数A所有质因子
int[] primesB = getNprime(B);   //数B所有质因子
int[] resultPrime = getCommonPrime(primesA,primesB);  //数A和数B的公共质因数
int maxCommonDivisor = 1;
System.out.println(A+"和"+B+"的公共质因数为：");
for(int i = 0;i < resultPrime.length;i++){
maxCommonDivisor *= resultPrime[i];
System.out.print(resultPrime[i]+"\t");
}
System.out.println();
System.out.print(A+"和"+B+"的最大公约数为："+maxCommonDivisor);
}

public static void main(String[] args){
System.out.println("请输入数字A和数字B的值：");
Scanner in = new Scanner(System.in);
int a = in.nextInt();
int b = in.nextInt();
getMaxCommonDivisor(a,b);
}
}

运行结果：
请输入数字A和数字B的值：
60
100和60的公共质因数为：
2    5
100和60的最大公约数为：20

请输入数字A和数字B的值：
48
60和48的公共质因数为：
2    3
60和48的最大公约数为：12

请输入数字A和数字B的值：
54
120和54的公共质因数为：
3
120和54的最大公约数为：6



展开全文
• 今天记录一下如何用埃拉托色尼筛选法实现输出小于某个数n的所有质数，大家都知道质数是除了自己和1之外的所有数整除的数。最粗暴的实现方法就是用两个for循环，在最里层进行取余操作，如果取余为0则不是质数。除此...
Greeting！今天记录一下如何用埃拉托色尼筛选法实现输出小于某个数n的所有质数，大家都知道质数是除了自己和1之外的所有数整除的数。最粗暴的实现方法就是用两个for循环，在最里层进行取余操作，如果取余为0则不是质数。除此之外，还可以用一种叫埃拉托色尼筛选法(the Sieve of Eratosthenes)的办法，节省内存和运算时间。埃拉托色尼筛选法的原理(1)先把1删除(现今数学界1既不是质数也不是合数)(2)读取队列中当前最小的数2，然后把2的倍数删去(3)读取队列中当前最小的数3，然后把3的倍数删去(4)读取队列中当前最小的数5，然后把5的倍数删去(5)读取队列中当前最小的数7，然后把7的倍数删去(6)如上所述直到需求的范围内所有的数均删除，剩下的就是质数图片来自百度百科实现代码代码由java语言实现，源代码来自 CS 61B (2014 Spring)：public static void printPrimes(int n) {boolean[] prime = new boolean[n + 1];                  // Numbered 0...n.int i;for (i = 2; i <= n; i++) {prime[i] = true;}for (int divisor = 2; divisor * divisor <= n; divisor++) {if (prime[divisor]) {for (i = 2 * divisor; i <= n; i = i + divisor) {prime[i] = false;                     // i is divisible by divisor.}}}for (i = 2; i <= n; i++) {                  //print the primeif (prime[i]) {System.out.print(" " + i);}}}代码原理分析这套code的特点在于，创造性地建立了大小为n+1的，bool类型的char数组。依据char的序号作为筛选质数的作为循环的数本体(从0到n)，然后根据对应的char数组里面的bool类型来判断是否为质数。True为是质数，False为不是质数。注意1：为什么要n+1个数组单位？因为在数组中，序号从0开始计数，所以我们要将数字大小定为n，数组的大小就必须为n+1。(在这里，序号0和1都是没有必要考虑的，原因见原理部分)在第一个循环中，我们假定所有的char数组暂时都为true(即0到n都为质数)。利用iteration，将所有队列中最小的数(2,3,5,7,11….)的倍数给删去，即下图表格所显示的值都不是质数，所以标为false。注意2：可以看出这里的divisor为质数从小到大一直到 (后面说明原因)，那么如何确定divisor呢？我们根据divisor为质数，可知某质数作为char的序号对应的bool类型为True。可使用if语句：if (prime[divisor])如果满足True，则进行下面的循环：for (i = 2 * divisor; i <= n; i = i + divisor){prime[i] = false;}例如，这里的4所对应的布尔数组已经在第一次循环中(2×2)被标为了false，因此只有这个char[]为true，才进行iteration，因此选出了队列中当前最小的数。作者用Excel画的渣图注意3：为什么divisor只要到 呢？我们看到图中标同样颜色的框，其实是重复的，事实上我们如果去除重复的话，表中的信息呈现一个倒三角形状。2从2×2开始，3从3×3开始，5从5×5开始等等，类似于我们小时候背的乘法口诀表。所以当divisor为   及附近时，要从 的平方开始，我们要求n以内的质数，再往上就没意义了。在代码段的最后一段中，剩下位置对应的数就是质数，因为在上一个操作中没有被删掉。利用循环输出标记仍为true的char所对应的位置序号。最终，我们就可以在屏幕中输出想要的n以内质数啦！
展开全文
• 前戏：本篇介绍一种特定数据范围内统计该段数据内所有质数的高效算法，埃拉托色尼筛选法。 正文： 1、埃拉托色尼筛选法埃拉托色尼筛选法(the Sieve of Eratosthenes)简称埃氏筛法，是古希腊数学家...
• def sieve_of_eratosthenes(n):#埃拉托色尼筛选法，返回少于n的素数 primes = [True] * (n+1)#范围0到n的列表 p = 2#这是最小的素数 while p * p &lt;= n:#一直筛到sqrt(n)就行了 if primes[p]:#如果没被筛...
• 埃拉托色尼筛选法 埃拉托色尼选筛法(the Sieve of Eratosthenes)简称埃氏筛法，是古希腊数学家埃拉托色尼(Eratosthenes 274B.C.～194B.C.)提出的一种筛选法。是针对自然数列中的自然数而实施的，用于求一定范围内...
• 这几天在学习算法和数据结构，在学习基本数据结构数组的时候（数组就是最基本的数据结构），偶然看到了一种利用数组求素数的方法，就是用的埃拉托色尼筛选法那么埃拉托色尼筛选法到底是什么方法呢？埃拉托色尼选筛法...
• 埃拉托色尼筛选法首先需要按顺序写出2到n中所有的数。然后把第一个元素画圈，表示它是素数，然后依次对后续元素进行如下操作：如果后面的元素是画圈元素的倍数，就画X，表示该数不是素数。在执行完第一步后，会得到...
• 埃拉托色尼筛选法（Eratosthenes Sieve）算法思想简单分析，java代码实现
• 今天记录一下如何用埃拉托色尼筛选法实现输出小于某个数n的所有质数，大家都知道质数是除了自己和1之外的所有数整除的数。最粗暴的实现方法就是用两个for循环，在最里层进行取余操作，如果取余为0则不是质数。除此...
• 埃拉托色尼筛选法： 任给一个整数N，筛选出一切不超过N的所有素数：  把不超过N的一切正整数按大小关系排成一串：  1 ，2 ，3， 4， .......，N 首先划去1，第一个留下的是 2，它是一个质数： 1， 2， 3， 4...
• 埃拉托色尼筛选法(the Sieve of Eratosthenes)简称埃氏筛法，是古希腊数学家埃拉托色尼(Eratosthenes 274B.C.～194B.C.)提出的一种筛选法。 是针对自然数列中的自然数而实施的，用于求一定范围内的质数，它的容斥...
• 埃拉托色尼筛选法计算素数个数 素数：指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。 int main() { int MAXNUM = 1000; // 在这里以1000为例 int num = 0; //num 为质数个数 int i, j; int ...
• // 埃拉托色尼筛选法- 求素数 void getprimes(int n) { int result[n]; for (int i = 0; i ; ++i) { result[i] = i + 1; } for (int j = 2; j * j ; ++j) { int idx = j; while(i
• package javaapplication3;import java.util.*;... * 埃拉托色尼筛选法(the Sieve of Eratosthenes)简称埃氏筛法 * 未优化 */ public class JavaApplication3 { public static void main(String[] args) {
• 快速筛选素数：埃拉托色尼筛选法 只有一行的算法：欧几里得算法求解最大公约数 求幂乘：反复平法法 筛选素数 小学的知识点，不解释了； bool isPrime(int d){//判断是否是素数 if(d==2) return true; if(d<2|...
• 方法一：简单方法 这个算法会检查给定整数x能否被2~x-1的整数整除，因此对于单一数据其复杂度为O（x），...方法三：埃拉托色尼筛选法 #include<iostream> #include<math.h> #define MAX 10000005 ...
• 素数处理-埃拉托色尼筛选法（埃式筛） 埃拉托色尼筛选法（The Sieve of Eratosthenes） 继欧拉筛之后，我今天补的一篇博客。名字太长了emm。简称就是埃式筛法。 埃筛只能解决1e7以下的问题。 因为空间受限。 这两种...
• 埃拉托色尼筛选法求一定范围内自然数中的素数： 1、首先取得大于2的所有自然数的数列。 2、在数列中去掉所有大于2并且可以被2整除的数字，得到新数列。 3、在新数列中去掉所有比第一位大但是可以被第一位数整除的...
• 埃拉托色尼筛选法是用来生成质数的经典计算机编程算法，一般用来衡量计算机的速度。 我们知道，质数是能被自己和1整除的整数。 2，3，5，7，11都是质数。 那么算法是如何实现质数的识别呢？ 1.2我们可以简化理解为：...

...