Integer Numbers in C

PTrenholme · 10-19-2005, 05:02 PM

Quote:

Originally posted by Mercurius
You are right, I was wrong 15 can be divided by 3. How do you suggest to compute if one number is prime or not?

Got it, thanks alot for the help. One last question about flowcontrol. Cant I do in C something like go to line 15?

Yes, but that kind of construct should be avoided. This works:

Code:

int gcd(int a, int b)
{
  int q, r;
  q = (a > b) ? a : b;
  r = (a < b) ? a : b;
  a = q;
  b = r;
  q = a % b;
  r = a - q *a;
  return (r == 0) ? q : gcd(b, r);
}

int euler(int n)
{
  int a = 0;
  int i = 1;
loop:
    a = a + (gcd(a, i) == 1) ? 1 : 0;
    i = i + 1;
    if (i > n) return a;
    goto loop;
}

but this is better

Code:

int gcd(int a, int b)
{
  int q, r;
  q = (a > b) ? a : b;
  r = (a < b) ? a : b;
  a = q;
  b = r;
  q = a % b;
  r = a - q *a;
  return (r == 0) ? q : gcd(b, r);
}

int euler(int n)
{
  int a = 0;
  for (int i = 1; i <= n; ++i) {
    a += (gcd(a, i) == 1) ? 1 : 0;
  }
  return a;
}

Caution: The above code is C++, not C, because of the declaration of i inside the for.

(FYI: the Euler function return the number of numbers less than "n" that are relativel prime to n. And the "gcd" function returns the "greatest common divisor" of two numbers. If the value is 1, the two numbers are "relatively prime." Notice that the "gcd" function is recursive, so it will fail for "large" numbers. [The code was for an algebra homework problem I was working on a few weeks ago.])

Mercurius · 10-19-2005, 07:11 PM

Why should the "goto" be avoided? It sounds fairly straight and simple to use...

perfect_circle · 10-19-2005, 08:03 PM

http://crasseux.com/books/ctutorial/...bout-goto.html

http://www.le.ac.uk/cc/tutorials/c/ccccgoto.html

http://www.its.strath.ac.uk/courses/...00000000000000

http://www.samspublishing.com/articl...&seqNum=4&rl=1

those are the first 4 results in google when searching for "C programming goto"

Mercurius · 10-19-2005, 08:11 PM

Well, all say not to use goto. Sure, it may look ugly, but come one, what would you prefer? Art or quick functionality? Or both? Why should anyone discard a function just beacause it's ugly??

perfect_circle · 10-19-2005, 08:33 PM

it's not only the ugliness in the problem. If you put 2 gotos in the code and you jump 40-50 lines up or down the program becomes hard to read and follow. Especially people who now learn C should not use it because they don't know where its OK to do this and where not. You can do everything without the goto.

But It's your code.....

enemorales · 10-20-2005, 03:53 AM

Just a clarification:

Testing if a number is prime or not isn't hard (It can be done in polynomial time). The hard part is to calculate the prime descomposition.

And, in any case, the problem isn't unsolvable. It is just "hard" in the sense that it takes a lot of time for the computer to be done. Here is a pseudo-algorithm for primality testing: If N is the number to be tested,

for i from 2 to sqrt(N): if i divides N then N isn't a prime number.

You can use the same idea to calculate the descomposition. The problem is that it takes quite long time (or at least almost every computer scientist thinks so).

perfect_circle · 10-20-2005, 07:31 AM

Quote:

Originally posted by enemorales
Just a clarification:

Testing if a number is prime or not isn't hard (It can be done in polynomial time). The hard part is to calculate the prime descomposition.

And, in any case, the problem isn't unsolvable. It is just "hard" in the sense that it takes a lot of time for the computer to be done. Here is a pseudo-algorithm for primality testing: If N is the number to be tested,

for i from 2 to sqrt(N): if i divides N then N isn't a prime number.

You can use the same idea to calculate the descomposition. The problem is that it takes quite long time (or at least almost every computer scientist thinks so).

I haven't stated it clear. What I meant is that there is no mathematical equation to check if a number is prime. And this is proven.

PTrenholme · 10-20-2005, 08:59 AM

Quote:

Originally posted by perfect_circle
I haven't stated it clear. What I meant is that there is no mathematical equation to check if a number is prime. And this is proven.

Actually, that depends on your definition of "mathematical equation." As you stated, the problem is solvable for any integer, and you even gave a procedure to follow to solve the problem.

I'd call that an "equation" in the general sense that it defines a map from the set of integers to the set of prime numbers.

jim mcnamara · 10-20-2005, 09:31 AM

FWIW - the fastest possible way to determine primaility is to create a static array with of all the prime numbers up to the limit of your variable's datatype. In other words, you calculate them once, then store them in code.

Then use bsearch on the array.

You can download a list of primes here if you don't want to calculate them:

http://www.totse.com/en/technology/s...y/prime10.html

It also has a simple C program to create those prime numbers, but running that code every time your program starts up is a bad idea in terms of performance. So keeping the primes in memory, though memory expensive (not good from ARM development), is the fastest possible implementation.

If you know the numbers input will always be small (say less than 8192) then use a seive and store the data in an array.
Here is an old version, I think it will compile on most machines:

http://www.fpx.de/fp/Software/Sieve.html download sieve.c

Mercurius · 10-20-2005, 09:54 AM

/*
*
* Dumb program that generates prime numbers.
*/
#include <stdio.h>
#include <stdlib.h>

main(){
int this_number, divisor, not_prime;

this_number = 3;

while(this_number < 10000){
divisor = this_number / 2;
not_prime = 0;
while(divisor > 1){
if(this_number % divisor == 0){
not_prime = 1;
divisor = 0;
}
else
divisor = divisor-1;
}

if(not_prime == 0)
printf("%d is a prime number\n", this_number);
this_number = this_number + 1;
}
exit(EXIT_SUCCESS);
}

This is from the C book, it prints all prime number between 3 and 10.000