求自然数n以内的质数
今天遇到这样一道题目：求自然数n以内的质数
经过观察以后，我觉得可以以下方式来求解：
将已求解的质数放入结果数组，判断下一个数是否是质数，只要将它除以质数结果数组，如果都不能被整除，那么这个数也是一个质数，放入结果数组中。
/*
* PrimeNumber.java
*
* Created on 2006年8月12日, 下午6:05
*
* This class is under Gnu GPL.
*/
package primenumber;
import java.io.IOException;
/**
* Get prime numbers.
*
* @author <a href=”guangquanzhang@gmail.com“>guangquanzhang</a>
*/
public class PrimeNumber {
/** Creates a new instance of PrimeNumber */
public PrimeNumber() {
}
/**
* @param n natural number, 1-n
* @return all prime numbers between 1 and n.
*/
public static void getPrime(int n) {
int[] primes = new int[n];
int primesSize = 0;
// its apparent that 1, 2 is prime numbers
primes[0] = 1;
primes[1] = 2;
primesSize = 2;
for(int i=3; i<n; i++) {
int j = 1;
for (; j < primesSize; j++) {
if(i%primes[j] == 0) {
break;
}
}
if(j == primesSize) {
primes[primesSize] = i;
primesSize++;
}
}
// print all prime numbers
for(int k = 0; k < primesSize; k++) {
System.out.println(k + “ : “ + primes[k]);
}
}
public static void main(String[] args) {
PrimeNumber.getPrime(24);
}
}
By javafuns on April 24, 2007 at 00:15 ·
Views: 1,827 · Permalink · RSS
Categorized in: Data Structure, Java · Tagged with: Algorithms, Java
Categorized in: Data Structure, Java · Tagged with: Algorithms, Java
(1 votes, average: 5.00 out of 5)
Loading ...
(
(4.00 out of 5)
on 2008/11/30 at 12:48
· Permalink
不错不错。。。。。。。
on 2008/11/30 at 12:49
· Permalink
怎么发表不了啊。。。。。。
on 2009/03/18 at 13:40
· Permalink
该问题其实有更好的算法：
http://www.math.utah.edu/classes/216/assignment-07.html
求质数的方式更为巧妙，更为合理
我当时怎么就没想到呢？:)