面试题求一到100w中的完数
面试题求1到100w中的完数
一个数如果恰好等于除它本身外的因子之和,这个数就称为"完数",也叫“完美数”。例如6=1+2+3.(6的因子是1,2,3)
面试题真的太无谓了,好像是在考数学题一般.
一个数如果恰好等于除它本身外的因子之和,这个数就称为"完数",也叫“完美数”。例如6=1+2+3.(6的因子是1,2,3)
package com.zhao.test; //不知性质做 public class WanShu { //limit 在10000之内就ok // 100000就用23秒 public void getResult(int limit) { long begin = System.currentTimeMillis(); for(int i=1;i<=limit;i++) { if(isWanShu(i)) System.out.println(i); } long end = System.currentTimeMillis(); long time = end-begin; System.out.println("time is:"+time); } //是完数 public boolean isWanShu(int num) { //判断条件 if(num==getTotal(num)) return true; return false; } //求所有积因子的和 public int getTotal(int num) { int sum = 0; for(int i=1;i<=num/2;i++) { if(num%i==0) sum +=i; } return sum; } public static void main(String[] args) { WanShu wanshu = new WanShu(); wanshu.getResult(100000); } }
package com.zhao.test; import java.util.ArrayList; //知道性质做long类型用尽也不用时间 public class CountTest { //是素数 public boolean isShuShu(long num) { for(long i=2;i<num;i++) { if(num%i==0) return false; } return true; } //求完数,参数为一质数 //公式wanshu = 2^(n-1)*(2^n-1) n为质数 //质数的一性质 p为质数时,2^p-1为质数 public long getWanShu(long shushu) { long result = (long) (Math.pow(2, shushu-1)*(Math.pow(2, shushu-1))); return result; } public void getResult(long limit) { long begin = System.currentTimeMillis(); long range = (long) Math.sqrt(limit); for(long i=2;i<=range;i++) { long wanshu=0; if(isShuShu(i)) { wanshu=getWanShu(i); if(wanshu<=limit) { System.out.println(wanshu); } else { break; } } } long end = System.currentTimeMillis(); long time = end-begin; System.out.println("time is:"+time); } public static void main(String[] args) { CountTest ct = new CountTest(); ct.getResult(1000000000000000000l); } }
面试题真的太无谓了,好像是在考数学题一般.