Finding Prime Numbers Up to N: A Scientific Approach

Click For Summary
SUMMARY

This discussion focuses on implementing an efficient algorithm to find all prime numbers less than or equal to a user-supplied integer N, specifically using the method of dividing N by all prime numbers less than the square root of N. The participants emphasize the importance of creating a function to verify whether a number is prime by checking divisibility against previously identified primes. An example provided is finding primes for N=60, illustrating the practical application of the discussed algorithm.

PREREQUISITES
  • Understanding of prime numbers and their properties
  • Familiarity with programming concepts and functions
  • Knowledge of the square root function and its application in algorithms
  • Basic algorithm design and efficiency considerations
NEXT STEPS
  • Implement a prime-checking function in Python using the Sieve of Eratosthenes
  • Explore the mathematical proof of why only primes up to sqrt(N) are needed for divisibility checks
  • Study algorithm optimization techniques for large values of N
  • Learn about time complexity analysis for prime number algorithms
USEFUL FOR

Students, educators, and software developers interested in algorithm design, particularly those focused on number theory and efficient computation of prime numbers.

TimNguyen
Messages
79
Reaction score
0
How would I write a program that finds all the prime numbers that are less than or equal to a "user-supplied" integer N, implementing the fact that I should only be dividing N by all prime numbers less than sqrt(N)?
 
Physics news on Phys.org
Don't sound like a [strictly-] MATLAB question... but more like a homework problem.

How would you do it by hand with (say) N=60?
 
there should be a function that checks whether a resulting calculation is an integer or not (or you can always make your own function).

That's the key to this.
 

Similar threads

Python Who can find the largest prime number with their own programmed code?
  • · Replies 28 ·
Replies
28
Views
5K
Graduate Is it required to use the Reimann function to solve the problem?
  • · Replies 8 ·
Replies
8
Views
2K
Graduate How should I write an account of prime numbers?
  • · Replies 5 ·
Replies
5
Views
2K
Comp Sci Finding Cousins of Giuga Numbers: Can You Solve This Prime Number Puzzle?
  • · Replies 32 ·
2
Replies
32
Views
5K
Finding large prime factors (number theory)
  • · Replies 2 ·
Replies
2
Views
1K
Graduate I think I discovered a pattern for prime numbers
  • · Replies 1 ·
Replies
1
Views
1K
What is the fastest algorithm for finding large prime numbers?
  • · Replies 14 ·
Replies
14
Views
3K
MHB Find the smallest positive integer N
  • · Replies 3 ·
Replies
3
Views
2K
High School Do Prime Numbers Follow a Pattern?
  • · Replies 23 ·
Replies
23
Views
4K
Prime Number Detection: Running Time of Algorithm
  • · Replies 4 ·
Replies
4
Views
2K