flat assembler
Message board for the users of flat assembler.

Index > Main > Tests for Primality

Author
Thread Post new topic Reply to topic
Tyler



Joined: 19 Nov 2009
Posts: 1216
Location: NC, USA
Tyler
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?
Post 28 Mar 2010, 11:55
View user's profile Send private message Reply with quote
baldr



Joined: 19 Mar 2008
Posts: 1651
baldr
Tyler,

No matter how're you coding, it's the algorithm that counts. Small Fermat theorem is handy.
Post 28 Mar 2010, 13:55
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17270
Location: In your JS exploiting you and your system
revolution
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.
Post 28 Mar 2010, 14:32
View user's profile Send private message Visit poster's website Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4633
Location: Argentina
LocoDelAssembly
When someone found "Primo" please post at least the search query text because I'm continuously unable to find it Smile
Post 28 Mar 2010, 14:48
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17270
Location: In your JS exploiting you and your system
revolution
LocoDelAssembly: Is a direct link good enough?

http://www.ellipsa.eu/
Post 28 Mar 2010, 14:55
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17270
Location: In your JS exploiting you and your system
revolution
Found with "q=Primo+primality+proving+program".
Post 28 Mar 2010, 14:57
View user's profile Send private message Visit poster's website Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4633
Location: Argentina
LocoDelAssembly
Yep, it is much more reachable now, thanks Very Happy
Post 28 Mar 2010, 17:13
View user's profile Send private message Reply with quote
Tyler



Joined: 19 Nov 2009
Posts: 1216
Location: NC, USA
Tyler
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?
Post 31 Mar 2010, 00:46
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17270
Location: In your JS exploiting you and your system
revolution
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.
Post 31 Mar 2010, 01:16
View user's profile Send private message Visit poster's website Reply with quote
Tyler



Joined: 19 Nov 2009
Posts: 1216
Location: NC, USA
Tyler
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.Smile 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.
Post 31 Mar 2010, 03:44
View user's profile Send private message Reply with quote
nop



Joined: 01 Sep 2008
Posts: 165
Location: right here left there
nop
Tyler wrote:
I would guess it would be quite a bit.
more than a bit
quite a few bytes in fact Laughing
Post 01 Apr 2010, 02:11
View user's profile Send private message Reply with quote
Tyler



Joined: 19 Nov 2009
Posts: 1216
Location: NC, USA
Tyler
Oh, you're funny! Wink Smile
There needs to be a sarcasm emoticon
Post 01 Apr 2010, 06:20
View user's profile Send private message Reply with quote
Tyler



Joined: 19 Nov 2009
Posts: 1216
Location: NC, USA
Tyler
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.
Post 28 Jul 2010, 03:06
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar.

Powered by rwasa.