w*****1
发帖数: 245 | 1 给个整数, return是不是prime: boolean isPrime(int n);
我知道的解法: <=2的数单独处理, 然后for(int i=3; i
if(n % i == 0)
return false;
}
return true;
有没有更优化的做法?? |
f*********5
发帖数: 576 | 2 what will u return if n=16?
【在 w*****1 的大作中提到】
: 给个整数, return是不是prime: boolean isPrime(int n);
: 我知道的解法: <=2的数单独处理, 然后for(int i=3; i: if(n % i == 0)
: return false;
: }
: return true;
: 有没有更优化的做法??
|
s*********t
发帖数: 1663 | 3 他说小于等于2单独处理
【在 f*********5 的大作中提到】
: what will u return if n=16?
|
I**A
发帖数: 2345 | 4 感觉速度上已经很优化了吧？
不过，code有问题
1)n<9, all are true
2)为嘛要i increase by 2, if n=16, it will return true as well
【在 w*****1 的大作中提到】
: 给个整数, return是不是prime: boolean isPrime(int n);
: 我知道的解法: <=2的数单独处理, 然后for(int i=3; i: if(n % i == 0)
: return false;
: }
: return true;
: 有没有更优化的做法??
|
f*********5
发帖数: 576 | 5 16属于那个系列的？
我认为他说的是n==1，n==2 直接return
【在 s*********t 的大作中提到】
: 他说小于等于2单独处理
|
f*********5
发帖数: 576 | 6 for的3项内容，我认为都有问题
for(int i=2; i<=sqrt(n); i++)
这样才对吧？
【在 w*****1 的大作中提到】
: 给个整数, return是不是prime: boolean isPrime(int n);
: 我知道的解法: <=2的数单独处理, 然后for(int i=3; i: if(n % i == 0)
: return false;
: }
: return true;
: 有没有更优化的做法??
|
s*********t
发帖数: 1663 | 7 RE
我居然连这么弱智的错误都没发现。。
彻底受打击了
【在 f*********5 的大作中提到】
: for的3项内容，我认为都有问题
: for(int i=2; i<=sqrt(n); i++)
: 这样才对吧？
|
I**A
发帖数: 2345 | 8 那，到底有没有更优化的办法？
【在 f*********5 的大作中提到】
: for的3项内容，我认为都有问题
: for(int i=2; i<=sqrt(n); i++)
: 这样才对吧？
|
h**6
发帖数: 4160 | 9 sieve可以一次性找出不超过n的所有质数，不过如果只判断一个数是不是质数，就用楼
主的办法再加个判断奇偶就可以了。 |
t***s
发帖数: 602 | 10 伊好像搞混了i和n..
【在 f*********5 的大作中提到】
: for的3项内容，我认为都有问题
: for(int i=2; i<=sqrt(n); i++)
: 这样才对吧？
|
|
|
f*********5
发帖数: 576 | 11 有点那个意思
貌似伊每次+2是想跳过偶数，其实这个idea不错的
【在 t***s 的大作中提到】
: 伊好像搞混了i和n..
|
a****j
发帖数: 8 | 12 if ((n & 1) == 0) {
return false;
}
const int m = sqrt(n);
for (int i=3; i<=m; i+=2) {
}
【在 f*********5 的大作中提到】
: for的3项内容，我认为都有问题
: for(int i=2; i<=sqrt(n); i++)
: 这样才对吧？
|
w*****1
发帖数: 245 | 13 sorry我for中间项的确漏了=.
没有更好方法了吗?? |
w*****1
发帖数: 245 | 14 what about generate prime numbers until n?
void printPrimes(int n);
查了半天网上好像都是Sieve of Eratosthenes, 一个老算法. |
I**A
发帖数: 2345 | 15 上次amazon phone刚刚让我code了这个
我就用了这个Sieve of Eratosthenes老方法
你们谁给看看这个复杂度怎么算
O(n*(sqrt(2)+sqrt(3)+sqrt(4)+...sqrt(n))
wiki上说是O(n(logn)(loglogn))，怎么算的？
唉，上次给了人家一个O(n), 后来我发email更正了说不是O(n)，可是也没给我个回音儿
－－－－－－－－－－－－－－－
//find all the prime numbers between 2 and n(inclusive)
public void findPrimes(int n){
if(n<2)
return;
boolean[] isPrime = new boolean[n+1];
//initialize the boolean array to true;
for(int i=2; i<=n; i++)
isPrime[i] = tru
【在 w*****1 的大作中提到】
: what about generate prime numbers until n?
: void printPrimes(int n);
: 查了半天网上好像都是Sieve of Eratosthenes, 一个老算法.
|
v******a
发帖数: 54 | 16
音儿
increase
【在 I**A 的大作中提到】
: 上次amazon phone刚刚让我code了这个
: 我就用了这个Sieve of Eratosthenes老方法
: 你们谁给看看这个复杂度怎么算
: O(n*(sqrt(2)+sqrt(3)+sqrt(4)+...sqrt(n))
: wiki上说是O(n(logn)(loglogn))，怎么算的？
: 唉，上次给了人家一个O(n), 后来我发email更正了说不是O(n)，可是也没给我个回音儿
: －－－－－－－－－－－－－－－
: //find all the prime numbers between 2 and n(inclusive)
: public void findPrimes(int n){
: if(n<2)
|
