本文介绍了有没有一种简单的算法可以确定X是否为素数?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我一直在尝试通过Euler项目工作,并且注意到一些问题要求您确定质数作为其一部分。

I have been trying to work my way through Project Euler, and have noticed a handful of problems ask for you to determine a prime number as part of it.


  1. 我知道我可以将x除以2、3、4、5,...,X的平方根,如果到达平方根,我可以(安全地)假设这个数字是素数。不幸的是,这种解决方案似乎很笨拙。

  1. I know I can just divide x by 2, 3, 4, 5, ..., square root of X and if I get to the square root, I can (safely) assume that the number is prime. Unfortunately this solution seems quite klunky.

我研究了更好的算法来确定数字是否为质数,但很快就会感到困惑。

I've looked into better algorithms on how to determine if a number is prime, but get confused fast.

有没有一种简单的算法可以确定X是否是素数,而不会使普通的程序员感到困惑?

Is there a simple algorithm that can determine if X is prime, and not confuse a mere mortal programmer?

非常感谢!

推荐答案

第一个算法非常好,在Project上使用了很多欧拉。如果您知道所需的最大数目,也可以研究Eratosthenes的筛子。

The first algorithm is quite good and used a lot on Project Euler. If you know the maximum number that you want you can also research Eratosthenes's sieve.

如果维护素数列表,您还可以优化第一个算法以仅用素数除直到数字的平方根。

If you maintain the list of primes you can also refine the first algo to divide only with primes until the square root of the number.

使用这两个算法(除法和筛分法),您应该可以解决问题。

With these two algoritms (dividing and the sieve) you should be able to solve the problems.

编辑:评论中指出的固定名称

Edit: fixed name as noted in comments

这篇关于有没有一种简单的算法可以确定X是否为素数?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

09-27 16:08