一道算法题目 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

一道算法题目

一道算法题目# JobHunting - 待字闺中

w*e2010-09-18 07:09

1 楼

Q:Given an array of positive integers how to calculate how many prime
numbers are in the array? How do you improve it if you know the array size
is 100k and the numbers are between 2k to 8k.
哪位大侠给说说怎么improve 呀？多谢。

i*e2010-09-18 07:09

2 楼

第一题可以用sieve来解决啊。http://en.wikipedia.org/wiki/Sieve_of_eratosthenes
我blog上也有贴过这问题，也贴了代码。
至于要怎么improve，你可以说清楚一些吗？是什么方面的improve呢？内存方面？还是
时间复杂度方面？

【在 w*****e 的大作中提到】

: Q:Given an array of positive integers how to calculate how many prime
: numbers are in the array? How do you improve it if you know the array size
: is 100k and the numbers are between 2k to 8k.
: 哪位大侠给说说怎么improve 呀？多谢。

w*e2010-09-18 07:09

3 楼

Thanks ihasleetcode,
Sieve method to find all prime numbers for n. By using it, my solution is
like following:
1. go through array A and find the maximum number MAX.
2. use sieve method to find all prime number smaller than MAX. and put
them
into a set (hashtable?)
3. go though the Array again and check whether each element is in the set.
~
O(nlogn) ?
If the array size is 100k and the numbers are between 2k to 8k. the
numbers in the set are the prime numbers in the range(2k,8k).
Correct me if I

m*n2010-09-18 07:09

4 楼

第一问，估计是想知道几种方法可以做，随便提上几种就行；第二问，当然是sieve找
出prime hash table最快。

i*e2010-09-18 07:09

5 楼

For the prime sieve method to work, you will need an array size of N (N is
the maximum number). Since you mentioned that the primes are between 2K and
8K, you only need array of size 8K for the prime sieve method to work.
Then you iterate through the 100K array one by one, and the prime sieve
array can tell you if a number is prime or not.
See below for code sample on how to implement. You might also want to read
Programming Pearls for a discussion of generating primes efficiently.
http://www.ih

【在 w*****e 的大作中提到】

: Thanks ihasleetcode,
: Sieve method to find all prime numbers for n. By using it, my solution is
: like following:
: 1. go through array A and find the maximum number MAX.
: 2. use sieve method to find all prime number smaller than MAX. and put
: them
: into a set (hashtable?)
: 3. go though the Array again and check whether each element is in the set.
: ~
: O(nlogn) ?