筛选法求素数Java代码和matlab代码实现
关于筛选法求素数的算法我就不介绍了，大家可以点这里查看相关资料查看相关资料，这里只是贴下粗糙的代码。
package info.lwjlaser.prime;import java.util.ArrayList;import java.util.List;public class Prime {public static void main(String [] args){int numCount = 100000000;long start = System.currentTimeMillis();getAllPrime(numCount);long end = System.currentTimeMillis();System.out.println((end-start)/1000.0);start = System.currentTimeMillis();getAllPrimeEfficient(numCount);end = System.currentTimeMillis();System.out.println((end-start)/1000.0);}/** * 判断给定的数是否是素数 * @param n * @return */private static boolean isPrime(int n){if(0 >= n){throw new IllegalArgumentException("数字小于0");}if(1 == n){return false;}if(2 == n){return true;}for(int i = 2; i < Math.sqrt(n) + 1; i ++){if(0 == n % i){return false;}}return true;}/** * 返回包含小于给定数的所有素数的链表 * @param n * @return */private static List<Integer> getAllPrime(int n){List<Integer> primes = new ArrayList<Integer>((int)Math.sqrt(n));for(int i = 1; i <= n; i++){if(isPrime(i)){primes.add(i);}}return primes;}/** * 返回包含小于给定数的所有素数的链表(使用筛选法) * @param n * @return */private static List<Integer> getAllPrimeEfficient(int n){List<Integer> primes = new ArrayList<Integer>((int)Math.sqrt(n));int [] nums = new int[n+1];for(int i = 0; i <= n; i++){nums[i] = i;}nums[0] = 0;nums[1] = 0;for(int i = 2; i <= n; i++){if(0 == nums[i]){continue;}else{for(int j = 2;; j++){int index = j * i;if(index > n){break;}nums[index] = 0;}}}for(int num : nums){if(0 != num){primes.add(num);}}return primes;}}function prime(a)tic;if a <= 0 || round(a)~=a || ~isreal(a)||length(a)~=1 disp('请输入正确的数'); return;endif 1 == a disp('没有素数'); return;endif 2 == a || 3 == a disp(a); return;endarraySize=a - 1;array=zeros(1,arraySize);for x = 1:arraySize array(x)=x+1;endindex = 1;first = array(index);while first^2 <= a% if isPrime(first) if 0 ~= first for y = index + 1 :arraySize if 0 == mod(array(y),first) array(y)=0; end end end index = index+1; first = array(index);endtotal = 0;for z=1:arraySize if 0 ~= array(z) fprintf('%d ',array(z)); total = total+1; endendfprintf('\n');fprintf('%d以内共有%d个素数\n',a,total);toc; 1 楼 貌似掉线 2011-12-03 楼主是刚从C转JAVA的？ 2 楼 lwjlaser 2011-12-04 貌似掉线 写道楼主是刚从C转JAVA的？