flat assembler
Message board for the users of flat assembler.

 Index > Main > Tests for Primality
Author
Tyler

Joined: 19 Nov 2009
Posts: 1216
Location: NC, USA
Tyler 28 Mar 2010, 11:55
If it matters, I'm actually coding in c++ for this one, but the ? applies to the method, not the code.

Is there a "pretty" way to test for primality or is it actually necessary to do something like this? I can think of plenty of ways to do it(ifs with mods was my first idea), but is there a purely methodical/mathematical way to know a # is prime?
28 Mar 2010, 11:55
baldr

Joined: 19 Mar 2008
Posts: 1651
baldr 28 Mar 2010, 13:55
Tyler,

No matter how're you coding, it's the algorithm that counts. Small Fermat theorem is handy.
28 Mar 2010, 13:55
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20299
revolution 28 Mar 2010, 14:32
It all depends upon how many tests you are doing and the size of the numbers you are testing. Very small numbers (up to 1G) can simply be stored in a bitmap for fast testing. Very big numbers require specialised algorithms and usually specialised form of numbers to work on. A program like Primo (google for it) can generate primality proofs for numbers up to tens of thousands of bits in size if you are working with numbers of that size.
28 Mar 2010, 14:32
LocoDelAssembly

Joined: 06 May 2005
Posts: 4624
Location: Argentina
LocoDelAssembly 28 Mar 2010, 14:48
When someone found "Primo" please post at least the search query text because I'm continuously unable to find it
28 Mar 2010, 14:48
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20299
revolution 28 Mar 2010, 14:55
LocoDelAssembly: Is a direct link good enough?

http://www.ellipsa.eu/
28 Mar 2010, 14:55
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20299
revolution 28 Mar 2010, 14:57
Found with "q=Primo+primality+proving+program".
28 Mar 2010, 14:57
LocoDelAssembly

Joined: 06 May 2005
Posts: 4624
Location: Argentina
LocoDelAssembly 28 Mar 2010, 17:13
Yep, it is much more reachable now, thanks
28 Mar 2010, 17:13
Tyler

Joined: 19 Nov 2009
Posts: 1216
Location: NC, USA
Tyler 31 Mar 2010, 00:46
Sorry I didn't respond sooner, but I ended just making a linked list of all the primes I found, and since I was searching sequentially and starting at 2, all I had to do was test the next number against all the previous primes, and if none of them divided into the number being tested, it was prime.

Is that way acceptable?
31 Mar 2010, 00:46
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20299
revolution 31 Mar 2010, 01:16
Tyler wrote:
Is that way acceptable?
Sure it is. If that is all you need then that is fine. It depends upon what you need to achieve. If you only want 1000 or so primes then that method will work great, easy to program and finished pretty quickly. If you need say 100 digit primes then you might have to start looking at different methods else with the trial division method you are using you will be waiting for eternity just to test one number.
31 Mar 2010, 01:16
Tyler

Joined: 19 Nov 2009
Posts: 1216
Location: NC, USA
Tyler 31 Mar 2010, 03:44
revolution wrote:

If you need say 100 digit primes then you might have to start looking at different methods else with the trial division method you are using you will be waiting for eternity just to test one number.

I doubt I'll encounter that problem, considering that I have no idea how to go about calculating numbers lager than a "double" in C/C++. I guess I could use something like http://sourceforge.net/projects/cpp-bigint/, but what good would that do me, since I don't understand it. If I was going to deal with numbers bigger than could be natively(by the language), I'd probably made some asm routines to be called from the C/C++ since asm's better at addressing memory directly.(without being limited by types)

Just a thought, imagine how much memory it would take to store all those primes leading up to the first hundred digit prime if I were to attempt to use said method on such a number. I would guess it would be quite a bit.
31 Mar 2010, 03:44
nop

Joined: 01 Sep 2008
Posts: 165
Location: right here left there
nop 01 Apr 2010, 02:11
Tyler wrote:
I would guess it would be quite a bit.
more than a bit
quite a few bytes in fact
01 Apr 2010, 02:11
Tyler

Joined: 19 Nov 2009
Posts: 1216
Location: NC, USA
Tyler 01 Apr 2010, 06:20
Oh, you're funny!
There needs to be a sarcasm emoticon
01 Apr 2010, 06:20
Tyler

Joined: 19 Nov 2009
Posts: 1216
Location: NC, USA
Tyler 28 Jul 2010, 03:06
http://cboard.cprogramming.com/general-discussions/128722-pluspluseureka.html - Read a couple of posts(It's not resolved in the first.). This could actually be useful.
28 Jul 2010, 03:06
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainTutorials and ExamplesDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsOS ConstructionIDE DevelopmentProjects and IdeasNon-x86 architecturesHigh Level LanguagesProgramming Language DesignCompiler Internals Other----------------FeedbackHeapTest Area

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou cannot attach files in this forumYou can download files in this forum