查找给定正整数中所有的质数

import java.util.ArrayList;


/*
 * 质数就是只能被1和本身整除的数字。
 * 请写出一个方法，在任意给定一个正整数A后，找出0到这个正整数A中存在的所有质数。
 */
public class PrimeNumber {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int inputNum = 20; //Prime numbers will be: 2, 3, 5, 7, 11, 13, 17, 19,
        ArrayList primeNumList = PrimeNumber.getPrimeNumber(inputNum);
        for (int i = 0; i < primeNumList.size();i ++)
        {
            System.out.print(primeNumList.get(i) + ", ");
        }
    }

    public static ArrayList getPrimeNumber(int inputNum)
    {
        ArrayList primeNumList = new ArrayList();
        //第一个循环遍历正整数A下除1外所有的正整数
        for (int i = 2; i <= inputNum; i++)
        {
            primeNumList.add(i);
            //内层循环判断第一个循环的当前整数是否是质数
            for (int j = i-1; j > 1; j--)
            {
                //当目前的整数i能够整除0,和i之间任一个整数时，这个数i不是质数，移除出数组。
                if (i%j == 0)
                {
                    primeNumList.remove(primeNumList.indexOf(i));
                    break;
                }
            }
        }
        
        return primeNumList;
    }
}

评论

1 楼 nikalan 2011-12-14  

效率太低了