Ask Your Question

What is the quickest method for generating a list of all prime numbers that are lesser than N?

asked 2022-10-02 11:00:00 +0000

plato gravatar image

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted

answered 2022-07-20 14:00:00 +0000

lalupa gravatar image

One quick method to generate a list of all prime numbers that are lesser than N is the Sieve of Eratosthenes:

  1. Create a list of all numbers from 2 to N.
  2. Start with the first prime number, 2, and cross out all multiples of 2 from the list (4, 6, 8, etc.).
  3. Move to the next unmarked number, 3, which is also prime, and cross out all multiples of 3 from the list (6, 9, 12, etc.).
  4. Continue this process, taking the next unmarked number as the next prime, and crossing out all its multiples.
  5. When you reach the square root of N, all remaining unmarked numbers are prime.

The resulting list will contain all prime numbers less than N.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account. This space is reserved only for answers. If you would like to engage in a discussion, please instead post a comment under the question or an answer that you would like to discuss

Add Answer

Question Tools


Asked: 2022-10-02 11:00:00 +0000

Seen: 12 times

Last updated: Jul 20 '22