A Sieve for Prime Based on Extension Form of Not Prime

• 作者: Gabriele Martino
• 来源期刊: 美国计算数学期刊(英文)
• 学科: 数学
• 关键词: PRIME NUMBER EQUATION SIEVE
• 年，卷（期）: 2013,（1）
• 页码范围: 86-89
• 页数: 4页
• 分类号: O1

摘要

This paper will illustrate two versions of an algorithm for finding prime number up to N, which give the first version complexity (1) where c1, c2 are constants, and N is the input dimension, and gives a better result for the second version. The method is based on an equation that expresses the behavior of not prime numbers. With this equation it is possible to construct a fast iteration to verify if the not prime number is generated by a prime and with which parameters. The second method differs because it does not pass other times over a number that has been previously evaluated as not prime. This is possible for a recurrence of not prime number that is (mod 3) = 0. The complexity in this case is better than the first. The comparison is made most with Mathematics than by computer calculation as the number N should be very big to appreciate the difference between the two versions. Anyway the second version results better. The algorithms have been developed in an object oriented language.