Thread: calculating if a number is a prime number or not

  1. #16
    Registered User
    Join Date
    Apr 2019
    Posts
    650
    trouble is with this approach to find all the primes smaller than 2 million it takes 45 seconds without stopping once past the square root of the number being tested. with an extra if statement to limit the search to a maximum of the square root of the number whole thing now takes 0.36 125 times faster!!
    Last edited by cooper1200; 1 Week Ago at 02:58 PM.

  2. #17
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,813
    For finding primes I have 2 ways - I ALWAYS use a sieve first.

    This is because you only have to check each number once at the start (without division) and then you just use a lookup table, and you don't end up with a loop in a loop

    The other (for large numbers) is - Check if even, and then a for loop that starts at 3, only checks odd numbers, and only checks divisors up to the square root of that number.

    The problem is when you use this method as a "IsPrime()" in another loop - It has to go through the inner loop for every number.


    For proof, solve a project Euler question with one method, and then the other.

  3. #18
    Registered User
    Join Date
    Apr 2019
    Posts
    650
    either way you end up using huge dollops of memory to store the numbers generated

  4. #19
    Registered User
    Join Date
    Feb 2019
    Posts
    359
    Quote Originally Posted by cooper1200 View Post
    either way you end up using huge dollops of memory to store the numbers generated
    If you want speed, there is no way to avoid this...

  5. #20
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,813
    The "for" loop does not use lots of memory, because it is checking on-the-fly, but it is very slow.

    The sieve is fast but needs a lot of memory

  6. #21
    Registered User
    Join Date
    Apr 2019
    Posts
    650
    either way if you are going to check for prime by dividing by primes you need a way to store the ones you have found. my arrays were getting close to 500000 elements each the size of int so nigh on 2mb

  7. #22
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,813
    If you divide by all odd numbers (like I do) you don't need to store the primes. The idea of this method is to not take up memory, so you comprise on run time

  8. #23
    Registered User
    Join Date
    Apr 2019
    Posts
    56
    Quote Originally Posted by Click_here View Post
    For finding primes I have 2 ways - I ALWAYS use a sieve first.
    Today it will be fun and possible to have fun,running two or more threads test primes with different algos
    How do you know when you are a Guru?
    When you can (code) C even blindfolded

  9. #24
    Registered User
    Join Date
    Apr 2019
    Posts
    56
    I am trying a vector approach
    How do you know when you are a Guru?
    When you can (code) C even blindfolded

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Calculating the nth prime number
    By joshlete in forum C Programming
    Replies: 11
    Last Post: 05-10-2017, 02:34 PM
  2. Calculating prime factor of a huge number.
    By Bakster in forum C Programming
    Replies: 15
    Last Post: 02-20-2009, 12:06 PM
  3. largest number prime number that can be produced...
    By ElemenT.usha in forum C Programming
    Replies: 8
    Last Post: 02-17-2008, 01:44 AM
  4. Calculating next prime number
    By anilemon in forum C Programming
    Replies: 8
    Last Post: 04-17-2006, 10:38 AM
  5. Replies: 3
    Last Post: 03-29-2005, 04:24 PM

Tags for this Thread