是erathosthens的筛最好的算法来生成素数从1到N? [英] is Sieve of erathosthens the best algorithm to generate prime numbers from 1 to N?

查看:110
本文介绍了是erathosthens的筛最好的算法来生成素数从1到N?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

有人问我在一次采访中这个问题。 我用筛埃拉托色尼概念和阵列实现的算法。

I was asked this question in an interview. I implemented an algorithm using sieve of eratosthenes concept and an array.

有没有更好的办法去了解这个问题, 对于那些谁不知道筛子,这里是链接:

Is there a better way to go about this question For those who dont know the sieve , here is the link:

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

编辑:最佳在时间和空间复杂度的方面。 我只是告诉他们,国有企业的缺点是空间复杂度。 因此,他们问我,如果我可以做一些事情。 以下是访谈如何着手: 1)实现了打印素数从1到n一个算法中 答:我实现了使用环境状况 2)这是去了解它的最佳方式 答:???

Best in terms of both time and space complexity. I just told them the flaw of SoE is space complexity. So they asked me if I could do something about it . Here is how the interview went about: 1) Implement a algo that prints prime numbers from 1 to n Ans: I implement using SoE 2) Is this the best way to go about it Ans: ???

推荐答案

嗯,这取决于你的意思最好的。埃拉托色尼的筛是很容易实现,但阿特金的筛会给你显著更好的性能

Well, it depends on what you mean by "best." The Sieve of Eratosthenes is very easy to implement, but the Sieve of Atkin will give you significantly better performance.

所以,如果最佳是指易于实施和理解,埃拉托色尼是要走的路。如果最佳的意思想炫耀自己的技能作为一个数学家,或有一个非常快速的算法,阿特金是要走的路。

So, if "best" means easy to implement and understand, Eratosthenes is the way to go. If "best" means want to show off your skills as a mathematician or have a very fast algorithm, Atkin is the way to go.

这篇关于是erathosthens的筛最好的算法来生成素数从1到N?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆