线性筛法找素数_sundowner_新浪博客



求0-N之间额素数,线性筛法是我见过的最好的算法了,具有线性时间复杂度。

现将算法思想描述如下。

说明:解决这个问题的诀窍是如何安排删除的次序,使得每一个非质数都只被删除一次

      中学时学过一个因式分解定理,他说任何一个非质(合)数都可以分解成质数的连乘积。例如,16=pow(2,4)18=2*pow(3,2)691488=pow(2,5)*pow(3,2)*pow(7,4)等。如果把因式分解中最小质数写在最左边,有16=pow(2,4)18=2*9,691488=pow(2,5)*21609,;换句话说,把合数N写成N=pow(p,k)*q,此时q当然是大于p的,因为p是因式分解中最小的质数。由于因式分解的唯一性,任何一个合数N,写成N=pow(p,k)*q的方式也是唯一的。

由于q>=p的关系,因此在删除非质数时,如果已知p是质数,可以先删除pow(p,1),pow(p,2),pow(p,3)…,接着找出比p大而没有被删除的数q,然后删除pow(p,1)q,pow(p,2)q,pow(p,3)q,…,一直到pq>N为止。

因为每个非质数都只被删除一次,可想而知,这个程序的速度一定相当快。依据GriesMisra的文章,线性的时间,也就是与N成正比的时间久足够了(此时要找出2N的质数)。


Read full article from 线性筛法找素数_sundowner_新浪博客


No comments:

Post a Comment

Labels

Algorithm (219) Lucene (130) LeetCode (97) Database (36) Data Structure (33) text mining (28) Solr (27) java (27) Mathematical Algorithm (26) Difficult Algorithm (25) Logic Thinking (23) Puzzles (23) Bit Algorithms (22) Math (21) List (20) Dynamic Programming (19) Linux (19) Tree (18) Machine Learning (15) EPI (11) Queue (11) Smart Algorithm (11) Operating System (9) Java Basic (8) Recursive Algorithm (8) Stack (8) Eclipse (7) Scala (7) Tika (7) J2EE (6) Monitoring (6) Trie (6) Concurrency (5) Geometry Algorithm (5) Greedy Algorithm (5) Mahout (5) MySQL (5) xpost (5) C (4) Interview (4) Vi (4) regular expression (4) to-do (4) C++ (3) Chrome (3) Divide and Conquer (3) Graph Algorithm (3) Permutation (3) Powershell (3) Random (3) Segment Tree (3) UIMA (3) Union-Find (3) Video (3) Virtualization (3) Windows (3) XML (3) Advanced Data Structure (2) Android (2) Bash (2) Classic Algorithm (2) Debugging (2) Design Pattern (2) Google (2) Hadoop (2) Java Collections (2) Markov Chains (2) Probabilities (2) Shell (2) Site (2) Web Development (2) Workplace (2) angularjs (2) .Net (1) Amazon Interview (1) Android Studio (1) Array (1) Boilerpipe (1) Book Notes (1) ChromeOS (1) Chromebook (1) Codility (1) Desgin (1) Design (1) Divide and Conqure (1) GAE (1) Google Interview (1) Great Stuff (1) Hash (1) High Tech Companies (1) Improving (1) LifeTips (1) Maven (1) Network (1) Performance (1) Programming (1) Resources (1) Sampling (1) Sed (1) Smart Thinking (1) Sort (1) Spark (1) Stanford NLP (1) System Design (1) Trove (1) VIP (1) tools (1)

Popular Posts