筛选法求素数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;
end
if 1 == a
    disp('没有素数');
    return;
end
if 2 == a || 3 == a
    disp(a);
    return;
end
arraySize=a - 1;
array=zeros(1,arraySize);
for x = 1:arraySize
    array(x)=x+1;
end
index = 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);
end
total = 0;
for z=1:arraySize
    if 0 ~= array(z)
       fprintf('%d ',array(z)); 
       total = total+1;
    end
end
fprintf('\n');
fprintf('%d以内共有%d个素数\n',a,total);
toc;

评论

2 楼 lwjlaser 2011-12-04  

貌似掉线 写道

楼主是刚从C转JAVA的？

不是，只是习惯这样的写花括号。

1 楼 貌似掉线 2011-12-03  

楼主是刚从C转JAVA的？