prime numbers

[Kevin190a]

Hello im a student in secondary grammar school , first of all sorry for my bad English i Will try my best to explain my problem.
My problem is, we got a homework to make an algoritm to say its number prime or not, and if not, we must write divisors of this number, pictures linked below how i tried, to write divisors anyway dont matter if prime or not,i use arrey for first in my life for display the divisiors but its doesn't work, i think there is a problem with indexing,but i dont know exatcly,all divisors is flashes at 0,  in normal situation i would ask my teacher but  because my teacher is spending his  Winter holiday and he Will come back next week, and we must to do this before he come back, i must ask for help here.i hope i get answear. 

[Mancho00 · Accepted solution]

Well, every time you enter the For Loop, you do a divide by zero on the first iteration.  That's probably going to affect things.

[mcduff]

Check out the following link

mcduff

[Bob_Schor]

What does it mean for an integer to be prime?  The usual answer is it must not be divisible by any positive (and non-zero) integer except 1 or itself.  So one (slow, maybe foolish) way to test "Is N prime?" is to try dividing N by 2, 3, ..., N-1 and see if there is any remainder.  If the answer is always "No", you are done.

This is very slow!  You can speed it up in several ways.  One is that you don't have to divide by every integer between 2 and N-1.  For example, if I want to know if 97 is prime, I only need to test those divisors < square root of 97.  Can you see why this is?  Here's a hint -- when you get an exact division (meaning the number is not prime), you have a Divisor and a Quotient, but no remainder (and you're done).  If you start with small Divisors, will the Divisor ever be bigger than the Quotient?  Under what conditions does the Divisor = Quotient?

Here's another trick -- you don't have to try every number!  You only need to try every prime number.  Again, do you understand why this is?  So if we could start out with a list of Prime Numbers, say all the Primes < 1000, we'd have a fast(er) way of finding all the primes less than (fill in this space, using the material from the previous paragraph).

I'll bet you have not heard of Eratosthenses, who made an early estimate of the size of the Earth, and invented the Sieve of Eratosthenes.  Here's how it works:

• Make a list of numbers from 2 to (say) 1000.
• Starting with the lowest number (2), "cross off" every 2 numbers.
• Starting with the next uncrossed-off number (3), "cross off" every (that many numbers).
• Continue until it seems reasonable to stop.
• The uncrossed-off numbers are all the Primes between 2 and N.

Now you can use this much-smaller set of trial divisors to find larger Primes.  As you find them, of course, you'll need to add them to your (growing) list of "Primes to try".  Or just use a larger Sieve.

Bob "Math is Fun" Schor

[altenbach]

You only need to test up to divisors less than half of your number.

Build the array of numbers at a conditional indexing tunnel.

Start the trial divisions with 2.

Your input number needs to be an integer (blue) because primes for floating point numbers are not defined.

There is a =0 primitive.

A more interesting problem would be to find all prime factors. See if you can do that (few changes needed!).

See how far you get, then search for my ni-week talk about benchmarking for more ideas.

[GerdW]

Hi,

one more hint for speed improvement (or less memory requirement) when sieving large amounts of primes:

For all numbers greater than 30 there are only up to 8 possible primes per block of 30 consecutive numbers (given by i×30 to i×30+29 for i>=1)!