题目:有一个数组,假设是{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;
}
}
分享到:
相关推荐
本书介绍了构建更优雅、更有效的软件的更省时技术、算法和技巧。这些方法都非常实用,而且很有趣,有时候会让人觉得意想不到,就像在解好玩的谜题一样。相信任何想要得到提高的程序员都能从本书中受益匪浅。 由在IBM...
求100~200内全部素数 自己 写的 一个小程序
算法-素数回文数的个数(信息学奥赛一本通-T1408).rar
能够快速计算1000万以内的素数个数,剔除2,3,5,7,11,13的倍数,减少计算量
java经典算法题例。参赛必做。 【程序14】 题目:两个乒乓球队进行比赛,各出三人。甲队为a,b,c三人,乙队为x,y,z三人。已抽签决定比赛名单。有人向队员打听比赛的名单。a说他不和x比,c说他不和x,z比,请编程序找...
暴力法 | 暴力法优化(取中间数)|暴力法优化(取平方根)|埃氏筛法|未知算法。五种算法的效率依次递增。在同一个Prime.java文件中都可以测试。
要求是:(查找算法、统计、求和、找 素数或质数) (1)在键盘上输入 1 个不小于 3 的自然数 N (例输入 10) , 求出其不到第 N 个自然数中奇数之和,并输出结果 (2)输出 1 到第 N 自然数中所有质数的个数 ...
C#取1000以内质数并按三角形输出 //2 //3 5 7 //11 13 17 19 23 //29 31 37 41 43 47 53 //59 61 67 71 73 79 83 89 97 //.................................................
3 如何判断一个数是否为质数(素数) 判断一个数是质数(素数),还是合数,可以根据它的约数的个数来确定:只有两个 约数的数,是质数;有三个或三个以上的约数的数是合数;有且只有一个约数的数既不 是质数也不是...
RSA加密算法 对文档进行加密 public void inputPQ() throws Exception { do { System.out.println("请输入素数p: "); BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in)); ...
1.分别求字符串中包含字母、空格、数字和其它字符的个数 2.求表达式结果 3.求素数 4.求天数 5.求一个正整数的各位数字之和 6.求最大公约数&最小公倍数 7.杨辉三角 8.兔子数列(斐波那契数列) 9.组成无重复数字的三位...
离散数学素数 此仓库包含有关素数的算法。
2012-06-12 12:18 1,154 N个数中1的个数.txt 2012-06-12 12:03 176,988 ODBCApiDataManager.rar 2012-06-12 11:50 54,935 PlayWithDataStructureSourceCode.zip 2012-06-12 13:00 23,174 random.rar 2012-06-12 12:...
【算法1-1-2】唯一的缺点是在计算各个质因子的个数的过程中无法同时生成质数表,因此质数表需要事先提供或另行计算。从这个例子中可以看到,在相同的数据结构上可以采用不同的算法,并产生不同的效果。 有时,算法的...
分别统计出包含英文字母、空格、数字和其它字符的个数.py,数据分类处理.py,数字颠倒.py,素数伴侣.py,提取不重复的整数.py,统计每个月兔子的总数.py,图片整理.py,整数与IP地址间的转换.py,质数因子.py,字串的连接最长...
本程序从外部读入1000个数据,按照一定的算法求出其中的素数的个数,并保存。
10-迷宫探险之鸡兔同笼11 - 11-迷宫探险之因数的个数12 - 12-迷宫探险之质数环13 - 13-迷宫探险之最大公约数14 - 14-迷宫探险之最小公倍数15 - 15-化龙池之余数定理16 - 16-化龙池之亲密数无pdf17- 17-最终之战之...
rsa算法设计程序 #if !defined(AFX_RSAA_H__081D9EE0_1245_11D5_80AC_0000E8810675__INCLUDED_) #define AFX_RSAA_H__081D9EE0_1245_11D5_80AC_0000E8810675__INCLUDED_ #if _MSC_VER > 1000 #pragma once #endif ...
2017校招真题校园招聘真题算法题(37道)Python源码,n个数里最小的k个.py,百度.py,不要二.py,餐厅.py,藏宝图.py,倒置字符串.py,地下迷宫.py,分苹果.py,分田地.py,合唱团.py,回文序列.py,饥饿的小易.py,计算糖果.py,...
在解密过程中,巧妙地运用了中国剩余定理,减少了求逆元的个数,提高了效率。特别地,根据该方案可得到改进的Paixao方案和Boneh方案,计算速度更快,效果更好。分析表明,此方案可以有效地减少计算复杂度,并且不会...