Testing if a number is prime or not

How can I start a function that could take an input and tell me if a number is prime or not?

Not really a job for an Arduino. If you are going to do learn to use one of the IDE's that do C/C++ (or better yet java) for the PC Try Netbeans - it's free.

You start a function by calling it.

Mark

Double-posting yet again? You never learn, do you?

You double/triple posted the other day, and this was one of your questions, as I remember.
Yep, here it is. Reply #1 in this combined thread:-
Function Program

Bloody rude.

holmes4:
Not really a job for an Arduino. If you are going to do learn to use one of the IDE's that do C/C++ (or better yet java) for the PC Try Netbeans - it's free.

You start a function by calling it.

Mark

What on earth makes that "Not really a job for an Arduino"? An Arduino is __more__than capable of doing the job...

Regards,
Ray L.

holmes4:
If you are going to do learn to use one of the IDE's that do C/C++

Besides what Ray said, Arduino is C++.

To test for primeness, try dividing by every possible prime factor that is less than the square root of the number.
If you are short on memory (like an Arduino), you can try dividing by 2 and every odd number. It shouldn't take more than 32000 loops to handle all numbers up to about 4billion, which is the largest integer you can do math on on an Arduino without going to a lot of effort. (I'll assume that this is a basic HW assignment, and you're not trying to prove primeness of 100-digit cryptographic key candidates...)

westfw:
If you are short on memory (like an Arduino), you can try dividing by 2 and every odd number.

Doing this takes almost zero memory. There's nothing you need to "remember" - it's a simple for loop, and as soon as you find a factor, you exit the loop. The program would be really, really tiny.

Regards,
Ray L.

westfw:
It shouldn't take more than 32000 loops to handle all numbers up to about 4billion, which is the largest integer you can do math on on an Arduino without going to a lot of effort. (I'll assume that this is a basic HW assignment, and you're not trying to prove primeness of 100-digit cryptographic key candidates...)

The biggest integer type you can do math on an Arduino easily is uint64_t, which has a range up to:
18.446.744.073.709.551.615

That is "a little" bit more than 4 billion, but much less than 100 digits.
64-bit integers are 19-20 decimal digits.

The only disadvantage with 64-bit integers is: There is no default function for output formatting, so you will have to use your own output formatting with 64-bit integers. But doing math with 64-bit integers is not the problem. Though dealing with uint64_t is relatively slow.

I've just run a little test to find the first prime number that is higher than 10 billion.

Starting with 1000000000000LL and counting up my Arduino UNO found the next prime number within 93 seconds calculation time:

1000000000039 is prime

So testing each number took a bit more than 2 seconds in that number range.
A 32-bit DUE board would surely be much faster with 64-bit calculations than a 8-bit controller.
If anybody is interested in the code, I could post it.
The algorithm is based on Wikipedias "naive primality test" pseudo code at

xoxoxo:
How can I start a function that could take an input and tell me if a number is prime or not?

Is this more of your homework? Just post your homework online and get someone else to do it for you. At what point do you actually earn your diploma or degree? Others are working hard to learn and you're trying to get us to do your work for you. What a waste.

Please folks, this is like the third or fourth homework problem this guy has posted with absolutely no effort on his own part. PLEASE, don't write him any code. You never know, this guy may be applying for a job where you work someday with his degree he never earned. And you'll have no way to know.

Delta_G:
Please folks, this is like the third or fourth homework problem this guy has posted with absolutely no effort on his own part. PLEASE, don't write him any code. You never know, this guy may be applying for a job where you work someday with his degree he never earned. And you'll have no way to know.

I second this. I intentionally avoided telling him how to do it for this very reason.
(That's why I linked back to the earlier thread, so it could be seen that it's homework.)

If you want big primes use the big number library

http://forum.arduino.cc/index.php?topic=85692.0

Delta_G:
... this guy may be applying for a job where you work someday ...

Or, he might wind up working at the company that designs the last pacemaker I'll ever need. Sure, my heirs can sue him, but I can't quite see how that works out well for me.

tmd3:
Or, he might wind up working at the company that designs the last pacemaker I'll ever need. Sure, my heirs can sue him, but I can't quite see how that works out well for me.

If he's in the US, he'll probably have an exemplary career in the government.

The U.S. has no corner on the "corrupt, incompetent and post hole dumb politician" market.

jremington:
The U.S. has no corner on the "corrupt, incompetent and post hole dumb politician" market.

Oh no, we're about to take it to a whole nutha level. Can't let the rest of the world out stupid us. Two words for ya. Donald Trump.

Don't forget Donald Duck.
.