loop for finding possible odd divisors

**JosAH** · Aug 14 '09, 07:01 PM

You're kidding us right? Nobody in his/her right mind writes code like that. Have a look at this:

Code:

#include <stdio.h>

static int isPrime(int n) {

	int i, inc= 2;

	if (n == 2 || n == 3) return 1;
	if (n%2 == 0 || n%3 == 0) return 0;

	for (i= 5; i*i <= n; i+= inc, inc= 6-inc)
		if (!(n%i)) return 0;

	return 1;
}

int main() {

	int i;

	for (i= 2; i < 10000; i++)
		if (isPrime(i))
			printf("%d\n");

	return 0;
}

kind regards,

Jos

**scienceman88** · Aug 14 '09, 07:35 PM

don't even understand that maybe that's why I never made it like that

**scienceman88** · Aug 14 '09, 07:36 PM

Also Jos I'm looking for a loop to shorten it not a sidenote of how crazy i am

**donbock** · Aug 15 '09, 12:22 AM

Originally posted by scienceman88

Also Jos I'm looking for a loop to shorten it not a sidenote of how crazy i am

I assume you're asking for a way to shorten the nest of if-statements. You could replace all of those if statements with a loop that starts at 3, increments by 2, and stops when the counter exceeds the square root of the number you're testing. That's not necessarily the best algorithm, but it is equivalent to the one you're using.

**Banfa** · Aug 15 '09, 12:23 AM

So you wouldn't call Jos loop rather shorter than your code then?

**Banfa** · Aug 15 '09, 12:33 AM

As an aside an alternitive to using a function to test to see if a number is prime if you are looking for primes in a given range of numbers is to just remove all the none primes from the list, something like

Code:

Populate LIST will all integers from 2 to 18 Quintillion

LOOP
    Get next NUMBER in list
    Remove all multiples of NUMBER except NUMBER*1 from the list
UNTIL END IS REACHED

At the end of the algorithm you have a list that just contains prime numbers in the range you start with. I do not know how efficient this algorithm is but I believe it isn't too in-efficient.

**hsheboul** · Aug 15 '09, 03:54 AM

Primality Testing

To test for a number whether it's a prime or not is "undecidabl e," and in terms of time efficiency, I think it's NP-Hard; NP stands for None-polynomial.

Odd factors? I don't exactly got what you mean by this!

In the below discussion, I'm using the Dynamic Programming technique.

To shorten the loop you are writing,
1. start with the 2 and 3 as the prime numbers, by definition.
2-a. get the next prime number,
2-b. add to the list of sentinels
3. process: do what ever you want.

So, talking about step 2 above, an efficient, but none-optimized, algorithm is the following, here is the "basic" idea.

From now on, I'll be using RO to stand for "Room for Optimization," and OT for "Optimizati on Technique being used/adopted."

Code:

/* define your list of sentinels, this BASIS list might change according to the OT. */

int sentinels[] =  {2, 3}  /* According to OT, 0 and 1 might be added */
int k = 2; /* the next avail slot in sentinels */
/* sentinels will be re-enlarged, re-allocate space using ralloc(), but less efficient to be re-allocated in the below function  */
function is_prime(integral_type n)
{
  /* k might be declared as static instead of being global above */
  if (n in sentinels)
    return TRUE;
  /* compute the square root of n */
  i = 3; /* RO */
  r = floor(square_root(n)); /* RO */
  while (i <= r && n % i) i++; /* Change of OT, then RO */
  if ( i < r) /* premature */
    return FALSE;
  sentinels[k++] = n;
  return TRUE;
}

Optimization fine point. The next available prime number is completely independent of the immediately preceding one and can never be used to test for the next available one. As thus, no room for optimization, but some improvement might be done -- no proof, ONLY ad hod -- for a specific problem domain, this sometimes works, but not absolute.

List of Sentinels. This list is incremental, need some specific point in the whole program as to be doubled in size, at some point this can't be done, due to the much wasted space, alternatively, some "predetermi ned" size, OT, can be added each time a space is needed.

Finding multiples of a prime and exclude them from testing.
Hope this helps out.

**donbock** · Aug 15 '09, 04:00 AM

Originally posted by scienceman88

don't even understand that [Message #2] maybe that's why I never made it like that

To test if a particular candidate number is prime you need only check if any of the prime numbers less than or equal to the square root of the candidate are factors. Nothing is gained by checking for nonprime factors; nothing is gained by checking for factors greater than the square root of the candidate. However, the effort to distinguish prime factors from nonprime factors is not trivial.

If you step through Jos' code you will notice that the trickiness involving inc causes only factors that are not divisible by 2 or 3 (other than 2 and 3 themselves) to be checked against the candidate. That is, Jos prunes out a small subset of the nonprime factors in order to speed up the code.

You could try to prune out a larger subset of nonprime factors, but at some point the additional pruning overhead swamps the savings from skipping factors.

**donbock** · Aug 15 '09, 04:20 AM

Originally posted by hsheboul

To shorten the loop you are writing,
1. start with the 2 and 3 as the prime numbers, by definition.
2-a. get the next prime number,
2-b. add to the list of sentinels
3. process: do what ever you want.

Code:

int sentinels[] =  {2, 3}  /* According to OT, 0 and 1 might be added */
int k = 2; /* the next avail slot in sentinels */
...
  sentinels[k++] = n;

The sentinels array is defined as having only two slots. The next prime added to the array (5) will be written past the end of the array -- wreaking havoc on the program. You either want to dynamically allocate sentinels and periodically realloc it or you want a large static allocation. For instance, if you know ahead of time that you intend to search for all primes less than N, you could define sentinels as follows (where Y = square root of N + 1; I'm too lazy to check if the +1 is actually needed):

Code:

int sentinels[Y] = {2,3};

Note: you have to compute Y yourself and type in the literal number; the compiler can't do it for you.

**hsheboul** · Aug 15 '09, 05:13 AM

Originally posted by donbock

The sentinels array is defined as having only two slots. The next prime added to the array (5) will be written past the end of the array -- wreaking havoc on the program. You either want to dynamically allocate sentinels and periodically realloc it or you want a large static allocation. For instance, if you know ahead of time that you intend to search for all primes less than N, you could define sentinels as follows (where Y = square root of N + 1; I'm too lazy to check if the +1 is actually needed):

Code:

int sentinels[Y] = {2,3};

Note: you have to compute Y yourself and type in the literal number; the compiler can't do it for you.

You are right Don, I was not that precise in writing the pseudo code.

Originally posted by donbock

if you know ahead of time that you intend to search for all primes less than N,

Ah, how large is that N, and how to find some info related to that N!

Two things can decide upon N:
(don't forget the problem is undecidable)
1. the hardware capabilities,
2. the time available

Check out

The Largest Known Primes (database sumary)

http://primes.utm.edu/largest.html

The oldest and best Internet source for information on record primes! Update daily. Do you want to know the largest prime and who found it? How about the largest twin prime? Or the largest Sophie Germain? Then check out this page. We have prime records, resources and references. Includes a searchable automated database of the 5000 largest known primes.

**JosAH** · Aug 15 '09, 06:05 AM

Originally posted by scienceman88

Also Jos I'm looking for a loop to shorten it not a sidenote of how crazy i am

Tadaa! Lines #10 and #11 are the loop you asked for. All primes (except 2 and 3) are a multiple of 6 plus or minus 1; that's exactly what that loop tests: i.e. if a number evenly divides by 6*x +- 1 it can never be a prime number.

kind regards,

Jos

**Banfa** · Aug 15 '09, 09:29 AM

Originally posted by JosAH

i.e. if a number evenly divides by 6*x +- 1 it can never be a prime number.

[slightly off topic silly and pedantic mode]Strictly speaking if a number is not a prime number it can "never" be a prime number there time is not a factor controlling if a number is prime or not :D
[/slightly off topic silly and pedantic mode]

Err Sorry

**JosAH** · Aug 15 '09, 09:44 AM

Originally posted by Banfa

[slightly off topic silly and pedantic mode]Strictly speaking if a number is not a prime number it can "never" be a prime number there time is not a factor controlling if a number is prime or not :D
[/slightly off topic silly and pedantic mode]

Err Sorry

You're wrong: there can be temporary prime numbers; e.g. they can be prime during the weekends or after 11:00pm or so. My hypothesis is that every number can be a temporary prime number but we don't know when it'll be prime and maybe they're also shy so they won't show their primeness when they're prime ...

kind regards,

Jos ;-)

**scienceman88** · Aug 15 '09, 11:32 AM

Okay
1)I barely understood your code jos
2)I tried to insert it to file instead and I couldn't get it to work.
3)N= max for unsigned long long integers or about 18,446,744,073, 709,551,615
4) you can use prime numbers before to calculate the next one it follows the sieve of eratosthenes( i know the sieve of atkin is faster but I don't understand it) and those sieves are the only known ways to find all primes except maybe primality testing each number

loop for finding possible odd divisors

loop for finding possible odd divisors

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment