分享
 
 
 

用C语言思想改写的用筛法求质数程序(第2修订版) 的一些源代码

王朝c/c++·作者佚名  2006-03-06
窄屏简体版  字體: |||超大  

原Java程序 Sieve.java

2006-02-18 13:24:01

/*

* Copyright (c) 2000 David Flanagan. All rights reserved.

* This code is from the book Java Examples in a Nutshell, 2nd Edition.

* It is provided AS-IS, WITHOUT ANY WARRANTY either expressed or implied.

* You may study, use, and modify it for any non-commercial purpose.

* You may distribute it non-commercially as long as you retain this notice.

* For a commercial use license, or to purchase the book (recommended),

* visit http://www.davidflanagan.com/javaexamples2.

*/

package com.davidflanagan.examples.basics;

/**

* This program computes prime numbers using the Sieve of Eratosthenes

* algorithm: rule out multiples of all lower prime numbers, and anything

* remaining is a prime. It prints out the largest prime number less than

* or equal to the supplied command-line argument.

**/

public class Sieve {

public static void main(String[] args) {

// We will compute all primes less than the value specified on the

// command line, or, if no argument, all primes less than 100.

int max = 100; // Assign a default value

try { max = Integer.parseInt(args[0]); } // Parse user-supplied arg

catch (Exception e) {} // Silently ignore exceptions.

// Create an array that specifies whether each number is prime or not.

boolean[] isprime = new boolean[max+1];

// Assume that all numbers are primes, until proven otherwise.

for(int i = 0; i <= max; i++) isprime[i] = true;

// However, we know that 0 and 1 are not primes. Make a note of it.

isprime[0] = isprime[1] = false;

// To compute all primes less than max, we need to rule out

// multiples of all integers less than the square root of max.

int n = (int) Math.ceil(Math.sqrt(max)); // See java.lang.Math class

// Now, for each integer i from 0 to n:

// If i is a prime, then none of its multiples are primes,

// so indicate this in the array. If i is not a prime, then

// its multiples have already been ruled out by one of the

// prime factors of i, so we can skip this case.

for(int i = 0; i <= n; i++) {

if (isprime[i]) // If i is a prime,

for(int j = 2*i; j <= max; j = j + i) // loop through multiples

isprime[j] = false; // they are not prime.

}

// Now go look for the largest prime:

int largest;

for(largest = max; !isprime[largest]; largest--) ; // empty loop body

// Output the result

System.out.println("The largest prime less than or equal to " + max +

" is " + largest);

}

}

SieveLT2.java

2006-02-18 13:26:16

以下内容引用自 涛23帖子

/*

* Copyright (c) 2000 David Flanagan. All rights reserved.

* This code is from the book Java Examples in a Nutshell, 2nd Edition.

* It is provided AS-IS, WITHOUT ANY WARRANTY either expressed or implied.

* You may study, use, and modify it for any non-commercial purpose.

* You may distribute it non-commercially as long as you retain this notice.

* For a commercial use license, or to purchase the book (recommended),

* visit http://www.davidflanagan.com/javaexamples2.

*/

//package com.davidflanagan.examples.basics;

/**

* This program computes prime numbers using the Sieve of Eratosthenes

* algorithm: rule out multiples of all lower prime numbers, and anything

* remaining is a prime. It prints out the largest prime number less than

* or equal to the supplied command-line argument.

**/

public class SieveLT2 {

public static void main(String[] args) {

int tm=(int)new java.util.Date().getTime();

// We will compute all primes less than the value specified on the

// command line, or, if no argument, all primes less than 100.

int max = 100; // Assign a default value

try { max = Integer.parseInt(args[0]); } // Parse user-supplied arg

catch (Exception e) {} // Silently ignore exceptions.

// Create an array that specifies whether each number is prime or not.

int maxhalf=(max+1)/2;

boolean[] isprime = new boolean[maxhalf+1]; //only save odd

int ct=0;

// Assume that all numbers are primes, until proven otherwise.

for(int i = 0; i <= maxhalf; i++)

{

isprime[i] = true;

// ct++;

}

// However, we know that 0 and 1 are not primes. Make a note of it.

isprime[0] = false; //1

isprime[1] = true; //3

// To compute all primes less than max, we need to rule out

// multiples of all integers less than the square root of max.

int n = (int) Math.ceil(Math.sqrt(max)); // See java.lang.Math class

// Now, for each integer i from 0 to n:

// If i is a prime, then none of its multiples are primes,

// so indicate this in the array. If i is not a prime, then

// its multiples have already been ruled out by one of the

// prime factors of i, so we can skip this case.

for(int i = 3; i <= n; i+=2) {

if (isprime[(i-1)/2]) //3y·¨??á?2????y // If i is a prime,

for(int j = 3*i; j <= max; j = j +i +i) // loop through multiples,

{

isprime[(j-1)/2] = false; // they are not prime.

// ct++;

}

}

for(int i = 0; i <= maxhalf; i++)

{

// System.out.println(i*2+1+":"+ isprime[i]);

}

// Now go look for the largest prime:

int largest=2;

if(max <=2)

{

largest=2;

}

else if((max%2==1)&&(isprime[(max-1)/2]))

{

// System.out.println("largest=max");

largest=max;

}

else

{

for(largest = max-1-(max %2); !isprime[(largest-1)/2]; largest-=2)

{

// ct++; // empty loop body

}

}

// Output the result

System.out.println("The largest prime less than or equal to " + max +

" is " + largest+" cycle time:"+ct);

System.out.println((int)new java.util.Date().getTime()-tm);

}

}

SIEVE7.C

2006-02-18 13:28:49

#include <stdlib.h>

#include <stdio.h>

#include <math.h>

//#define getisp(i) (isprime[(i)/8]>>((i)%8))&0x1

/*

#define setisp(i,j) j?(isprime[(i)/8]|=(0x1<<((i)%8))):(isprime[(i)/8]&=~(0x1<<((i)%8)))

*/

#define getisp(i) (isprime[(i)>>3]>>((i)&0x7))&0x1

int main(int argc, char *argv[])

{

int max = 100; // Assign a default value

max =abs(atoi(argv[1]));

// Create an array that specifies whether each number is prime or not.

int maxhalf=(max+1)/2;

unsigned char* isprime= (unsigned char*)malloc(maxhalf/8*2/3+2); //only save odd

int ct=0;

int i;

// Assume that all numbers are primes, until proven otherwise.

for(i = 0; i <= maxhalf/8*2/3+1; i++)

{

isprime[i] = 255;

// ct++;

}

// However, we know that 0 and 1 are not primes. Make a note of it.

//isprime[0] = 0; //1

//setisp(0,0);

isprime[0]&=~(0x1) ; //

//isprime[1] = 1; //3

//setisp(1,1);

//isprime[0]|=(0x2) ;

// To compute all primes less than max, we need to rule out

// multiples of all integers less than the square root of max.

int n = (int) ceil(sqrt(max)); // See java.lang.Math class

// Now, for each integer i from 0 to n:

// If i is a prime, then none of its multiples are primes,

// so indicate this in the array. If i is not a prime, then

// its multiples have already been ruled out by one of the

// prime factors of i, so we can skip this case.

char _3times=0;

i=(max-1)/2;

char i1=0;

/* for(int j = 4; j <=i ; j +=3) //set all 3's times

{

isprime[(j)>>3]&=~(0x1<<((j)&0x7));

}

int m= (n-1)/2;

int k=(max-1)/2;

for( i = 2; i <= m; i++)

{

if(++i1==3) //skip when i is 3's times

{

i1=0;

continue;

}

if(getisp(i))

{

_3times=((i<<2)+1)%3; //(2*(2*i+1)%3-1)

for(int j = i*(2*i+2); j <= k; j = j +i +i+1)

{

if(++_3times==3) //skip when j is 3's times

{

// printf("skip i=%d,j=%d%,%d\n",2*i+1,2*j+1,_3times);

_3times=0;

continue;

}

if(getisp(j)) //good idea

isprime[(j)>>3]&=~(0x1<<((j)&0x7));

//else

//ct++;

}

}

}

*/

int Flag=1;

for( i = 5; i <= n; i+=2)

{

if(++i1==3) //skip when i is 3's times

{

i1=0;

continue;

}

int m=(i-1)/2;

if (getisp(m)) // If i is a prime,

{

_3times=(i+i)%3-1; //(nod * nod )%3 all ==1

for(int j = i*i; j <= max; j = j +i +i) // loop through multiples,

{

if(++_3times==3) //skip when j is 3's times

{

// printf("skip i=%d,j=%d%,%d\n",i,j,_3times);

_3times=0;

continue;

}

// int k=(j-1)/2;// they are not prime.

int k= (j+1)/2*6+Flag;

Flag=-Flag;

if(getisp(k)) //good idea

{

isprime[(k)>>3]&=~(0x1<<((k)&0x7)); // they are not prime.

}

else

{

//printf("cat i=%d,j=%d%,%d\n",i,j,_3times);

ct++;

}

}

}

}

/*

for( i = 3; i <= n; i+=2)

{

int m=(i-1)/2;

if (getisp(m)) // If i is a prime,

{

for(int j = i*i; j <= max; j = j +i +i) // loop through multiples,

{

int k=(j-1)/2;// they are not prime.

if(getisp(k)) //good idea

isprime[(k)/8]&=~(0x1<<((k)%8)); // they are not prime.

//ct++;

}

}

}

*/

/*

int m= (n-1)/2;

int k=(max-1)/2;

for( i = 1; i <= m; i++)

{

//ct++;

if(getisp(i))

{

for(int j = i*(2*i+2); j <= k; j = j +i +i+1)

{

if(getisp(j)) //good idea

isprime[(j)>>3]&=~(0x1<<((j)&0x7));

//else

//ct++;

}

}

}

*/

/*

int k=(max-1)/2;

for(int u=0;u<=k;u++)

{

printf("%d:%d\n",u*2+1,getisp(u));

}

*/

// Now go look for the largest prime:

int largest=2;

if(max <=2)

{

largest=2;

}

else if((max%2==1)&&(getisp((max-1)/2)))

{

largest=max;

}

else

{

//for(largest = max-1-(max %2); ; largest-=2)

for(i=maxhalf/8*2/3;i>=0;i--)

{

// ct++; // empty loop body

// int k=(largest-1)/2;

int k= (i)/2*6+Flag;

Flag=-Flag;

if(getisp(k))

{

largest=k;

break;

}

}

}

// Output the result

free(isprime);

printf("The largest prime less than or equal to %d is %d, cycle time:%d\n" ,max, largest,ct);

return 1;

}

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有