新郎军事太没节操了，捏造了一堆扯淡的军事博客# Joke - 肚皮舞运动
c*w
1 楼
题目是打印n个质数。
请问最简单的这种方法，时间复杂度是多少？谢谢
每一次计算到一个n的数，都要和n个做n个判断所以是n^n吗
/**
* naive way.
* I think it takes O(n^n) time?
*/
public static void prime(int n) {
boolean[] primes = new boolean[n + 1];
for (int i = 2; i < primes.length; i++) {
if (isPrime(i)) {
primes[i] = true;
}
}
print(primes);
}
public static boolean isPrime(int num) {
for (int j = num - 1; j > 1; j--) {
if (num % j == 0) {
return false;
}
}
return true;
}
请问最简单的这种方法，时间复杂度是多少？谢谢
每一次计算到一个n的数，都要和n个做n个判断所以是n^n吗
/**
* naive way.
* I think it takes O(n^n) time?
*/
public static void prime(int n) {
boolean[] primes = new boolean[n + 1];
for (int i = 2; i < primes.length; i++) {
if (isPrime(i)) {
primes[i] = true;
}
}
print(primes);
}
public static boolean isPrime(int num) {
for (int j = num - 1; j > 1; j--) {
if (num % j == 0) {
return false;
}
}
return true;
}