小算法：求素数包的个数

题目：有一个数组,假设是{2,3}。。那么他的子集数包括{2}{3}{2,3}，这个称为子包。每个子包的数据和是2，3，5。它们都是素数，那就叫素数包。现在设计个程序，入口是数组，出口是数字（素数包的个数）。

分析：这里面涉及到2个知识点，一个是求所有子集，一个是求素数。其实就是将两个小知识点融合了一下。

    所有子集数可以用二进制组合的方式来求。比如求一个集合{1,2,3}的所有子集，如果一个元素在子集中出现，我们记为1，否则记为0。则{1,2,3}的所有子集可以表示为：

十进制数　         二进制数　           子集

0            =>   0 0 0              =>   {}

1            =>   0 0 1              =>   {3}

2            =>   0 1 0              =>   {2}

3            =>   0 1 1              =>   {2,3}

4            =>   1 0 0              =>   {3}

5            =>   1 0 1              =>   {1,3}

6            =>   1 1 0              =>   {1,2}

7            =>   1 1 1              =>   {1,2,3}

正好2的3次方个。按照要求，我们将空集去掉。

得到了子集，求和就轻而易举了。

 

    求素数有很多方法，如果是笔试或面试时遇到，可能最简单的是最有效的。

    程序代码：

public class Test {

    public static void main(String[] args) {
        int[] array = {2, 3, 4, 5, 6};
        System.out.println(test(array));
        System.out.println();
        array = new int[]{2, 3};
        System.out.println(test(array));
    }

    public static int test(int[] array) {
        int result = 0;
        int limit = (int) Math.pow(2, array.length);
        for (int i = 1; i < limit; i++) {
            int sum = 0;
            for (int j = 0; j < array.length; j++) {
                int num = i >> j;
                sum += (array[j] * (num & 1));
            }
            if (checkPrim(sum)) {
                result++;
            }
        }
        return result;
    }

    public static boolean checkPrim(int number) {
        for (int i = 2; i * i <= number; i++) {
            if (number % i == 0) {
                return false;
            }
        }
        return true;
    }
}

  

评论

3 楼 ZangXT 2009-10-15  

hunter4java 写道

有一个数组,假设是{2,3}。。那么他的子集数包括{2}{3}{2,3}，这个称为子包。每个子包的数据和是2，3，5。它们都是素数，那就叫素数包。

不是要求每个子集的和是素数才是素数包吗？ 那你怎么只求了一次全部和是素数就判定该子集为素数呢？

比如 3，4，6 你计算出来却是素数包!!!
这个明显不是素数包吧。（应该还要对这个子集包，判断它的所有子集是否是素数，比如4和6就明显不是素数。）

没要求算元素，就是看和是否为素数，3，4，6和为13，当然是素数。

“每个子包的数据和是2，3，5。它们（前面说的和）都是素数，那就叫素数包。”

2 楼 hunter4java 2009-10-15  

hunter4java 写道

有一个数组,假设是{2,3}。。那么他的子集数包括{2}{3}{2,3}，这个称为子包。每个子包的数据和是2，3，5。它们都是素数，那就叫素数包。

不是要求每个子集的和是素数才是素数包吗？ 那你怎么只求了一次全部和是素数就判定该子集为素数呢？

比如 3，4，6 你计算出来却是素数包!!!
这个明显不是素数包吧。（应该还要对这个子集包，判断它的所有子集是否是素数，比如4和6就明显不是素数。）

说详细一点： 比如 {3，4，6} 你计算出来却是素数包!!!
你只判断了他的最大子集{3，4，6}的和是素数，其他所有子集，如{3}，{4}，{6}，{3，4}等等却没有做判断。

1 楼 hunter4java 2009-10-15  

有一个数组,假设是{2,3}。。那么他的子集数包括{2}{3}{2,3}，这个称为子包。每个子包的数据和是2，3，5。它们都是素数，那就叫素数包。

不是要求每个子集的和是素数才是素数包吗？ 那你怎么只求了一次全部和是素数就判定该子集为素数呢？

比如 3，4，6 你计算出来却是素数包!!!
这个明显不是素数包吧。（应该还要对这个子集包，判断它的所有子集是否是素数，比如4和6就明显不是素数。）