Prime numbers

This is a discussion on Prime numbers within the C++ Programming forums, part of the General Programming Boards category; Originally Posted by execute That would not make it any faster. I timed it. Odd numbers are faster up to ...

  1. #16
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by execute View Post
    That would not make it any faster. I timed it.
    Odd numbers are faster up to the sqrt of the function is the best way.
    As long as your prime numbers fit in the L1 (or L2) cache of the processor, it's faster to test only prime numbers, because only roughly one in three odd numbers is a prime (one in three odd numbers is divisible by 3, and only one of the other two are most of the time a prime), and reading an one value out of an array and dividing by that is quicker than performing two divide operations on ALL modern processors.

    If you have a HUGE number of primes, then it's better to continue from the largest that fits in the cache with every other number, since just incrementing a number is faster than reading from the memory outside of the processor.

    --
    Mats
    Last edited by matsp; 12-11-2008 at 04:42 PM.
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  2. #17
    Registered User
    Join Date
    Apr 2006
    Posts
    137
    I suppose so, I never thought of using that method, and I doubt anyone would require that sort of intensive coding for any standard prime number involving project :P. Good job on whoever thought of it.
    ★ Inferno provides Programming Tutorials in a variety of languages. Join our Programming Forums. ★

  3. #18
    Banned
    Join Date
    Dec 2008
    Location
    Maputo, Mozambique
    Posts
    82
    Soma u so craycee. u maked me laffing my arse uff. U can reed sum info on da wikipedia 4 algorithms of primes.

  4. #19
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,230
    This is correct, that's what I meant by fastest, didn't know anyone would use that sort of method.
    This is a sieve. It is a slow sieve. The complexity guarantees that the more primes you need the slower it will be compared to many other prime sieves.

    Why are you spamming phantom?
    I wasn't. It was wishful thinking...

    U can reed sum info on da wikipedia 4 algorithms of primes.
    You use AOL don't you?

    I suggest you both benchmark this against a standard implementation of "Sieve of Erastothenes" with sets sizes of 10, 100, 1000, and 10,000.

    Soma

  5. #20
    Banned
    Join Date
    Dec 2008
    Location
    Maputo, Mozambique
    Posts
    82
    But da prime sleave uses a lots of memories.

  6. #21
    Registered User
    Join Date
    Apr 2006
    Posts
    137
    I'd rather not have a pointless debate about what a Sieve is or is not in terms of programming.
    But I believe it's used for TEA!

    The algorithm I talked about was the fastest available for most average programmers (I wasn't trying to say that no one can make faster) that is not using the complex L1/L2 cache method.
    ★ Inferno provides Programming Tutorials in a variety of languages. Join our Programming Forums. ★

  7. #22
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,635
    Before you guys get too excited, look again: whiterebbit is working on a problem that involves finding the largest prime factor, not finding if the number is prime (though coincidentally a prime is its largest prime factor). Just coming up with a primality testing algorithm is not enough (though a prime factoring algorithm will certainly work).
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Logical errors with seach function
    By Taka in forum C Programming
    Replies: 4
    Last Post: 09-18-2006, 05:20 AM
  2. Replies: 18
    Last Post: 11-04-2005, 01:41 PM
  3. prime numbers, counters, help!
    By vege^ in forum C++ Programming
    Replies: 1
    Last Post: 03-10-2003, 03:32 PM
  4. Prime numbers
    By Lazy Student in forum C Programming
    Replies: 12
    Last Post: 05-14-2002, 05:53 AM
  5. Homework help
    By Jigsaw in forum C++ Programming
    Replies: 2
    Last Post: 03-06-2002, 04:56 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21