Quote:
Code:
int gcd(int a, int b) Code:
int gcd(int a, int b) (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.]) |
Why should the "goto" be avoided? It sounds fairly straight and simple to use...
|
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" |
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??
|
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..... |
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). |
Quote:
|
Quote:
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. |
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 |
/*
* * 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 |
All times are GMT -5. The time now is 05:35 PM. |