微众银行笔试题
第二题是求N以内所有是质数的幂的数字的个数
为啥只AC了30%呢，感觉代码没问题来着
2018-04-16 21:08 已编辑 东南大学 算法工程师
关注
全部评论
Maybe66
西安电子科技大学 C++
先判断素数与否 然后把素数的幂次全部加进去
华为挺好的
合肥共达职业技术学院 C++
我感觉是丑数的变种
Rhys_Wu 楼主
楼主 东南大学 算法工程师
#include<iostream> #include<cstring> using namespace std; int isPrime[1001]; bool func(int num){ for (int i = 2; i < num; i++){ if (num%i == 0) isPrime[num] = 0; } if (isPrime[num] == -1) { isPrime[num] = 1; return true; } for (int i = 2; i < num; i++){ if (isPrime[i] == 1){ int buf = i; while (buf <= num){ if (buf == num) return true; buf *= i; } } } return false; } int main(){ int n; cin >> n; int res = 0; memset(isPrime, -1, 1001); for (int i = 2; i <= n; i++){ if (func(i)) res++; } cout << res; return 0; }
Rhys_Wu 楼主
楼主 东南大学 算法工程师
有没有老哥看看代码的
侠客小虎
南京理工大学 Java
package 微众;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class Main2 {
public static void main(String[] args) {
//求指定范围内的素数和由素数组成幂次数
Set <Integer> set = new HashSet <>();
Scanner sc = new Scanner(System.in);
int n=sc.nextInt();
//使用标记法
boolean [] isPrime=new boolean[n+1];
for(int i=2;i<=n;i++){
isPrime[i]=true;
}
for(int i=2;i*i<=n;i++){
if(!isPrime[i]){
continue;
}
for(int j=i*i;j<=n;j+=i){
isPrime[j]=false;
}
}
//统计素数
for(int i=2;i<=n;i++){
if(isPrime[i]){
set.add(i);
//对该数进行幂次运算
for(int j=1;Math.pow(i,j)<=n;j++){
//将幂次装入
set.add((int) Math.pow(i,j));
}
}
}
System.out.println(set.size());
}
}
相关推荐
