September 2nd, 2010, 02:39 PM

Conventional?
I have a few quick questions relating to a program I just wrote (very simple, for my own practice only). The first is, is there a way to check the highest value an int can go to, so I can warn the user not to enter that number or more?
Secondly, if you have a couple of minutes, can you quickly review this short piece of code and let me know if it is "Conventional C", the only other language I've learnt was object orientated so the style was completely different, I'd like to make sure I'm not forcing that onto another language.
Finally, are there any "mistakes" in this code that don't stop it working, but would cause problems later, or not be the best way to do something.
Code:
#include <strings.h>
#include <stdio.h>
int is_prime(int num);
int main() {
int num;
int finish;
scanf( "%d", &finish);
for(num=2;num<=finish;num++){
if (is_prime(num)){
printf("%d\n",num);
}
}
}
int is_prime(int num){
int divisor;
for(divisor=2;divisor<=num/2;divisor++){
if (num%divisor==0){
return 0;
}
}
return 1;
}
Sorry if this is unreasonable in any way.
Thanks a lot.
Angus
September 2nd, 2010, 02:57 PM

I cannot answer your first question, but the last part i'm curious about:
Someone correct me if i'm wrong, but shouldn't this:
Code:
int is_prime(int num){
int divisor;
for(divisor=2;divisor<=num/2;divisor++){
if (num%divisor==0){
return 0;
}
}
return 1;
}
be declared as a float instead of an int?
up at the top he declares it as:
Code:
int is_prime(int num);
shouldn't that be changed to:
Code:
float is_prime(int)
Is that wrong, or is it correct?
Comments on this post
September 2nd, 2010, 03:28 PM

For the range limits of a builtin data type, use the limits.h header file. Consult the macro definitions therein such as INT_MAX, INT_MIN, UINT_MAX, etc.
September 2nd, 2010, 03:37 PM

Originally Posted by dwise1_aol
For the range limits of a builtin data type, use the limits.h header file. Consult the macro definitions therein such as INT_MAX, INT_MIN, UINT_MAX, etc.
Thanks a lot, any comments on the code or is it fine for my current level?
September 2nd, 2010, 03:46 PM

Ok, thanks for sharing that dwise1. I'll remember that. I've not really worked with things like that, and i'm always eager to learn, and that was a good pointer.
September 2nd, 2010, 03:48 PM

I can break it with two keystrokes.
Functionality rules and clarity matters; if you can work a little elegance in there, you're stylin'.
If you can't spell "u", "ur", and "ne1", why would I hire you? 300 baud modem? Forget I mentioned it.
September 2nd, 2010, 03:52 PM

1. its int main, but you never returned an integer?
2. Just in case, in visual studio's the macros are named a bit different, look it up. For example: INT_MAX is _TMP_MAX_S
September 2nd, 2010, 04:15 PM

The code got some loopholes like:
1. Not checking the return value of scanf
Think about what would happen if the user enters non numeric character for example.
scanf
2. Not returning a meaningful value from main,
but aside from that the algorithm you use can be made more efficient. If it is of any interest to you you can continue reading or just use these wikipedia pages:
Sieve of Eratosthenes
Trial Division
first Lets look at the following somewhat improved primality testing function:
c Code:
unsigned isPrime (unsigned n) {
if (n == 2)
return 1;
if (n < 2  (n % 2 == 0))
return 0;
for (unsigned i = 3; i*i < n; i += 2)
if (n % i == 0)
return 0;
return 1;
}
1. If a number is even it's obviously not prime, so we're only have to check the remaining odd numbers for primality, which theoretically cuts the number of tests to half, of course you can argue that we could also exclude all the numbers divided by 3, and by 5 and so on... (which will lead us to the next method which I'm going to show you).
2. It is sufficient to test all the odd numbers up until the square root of n, because if x is a factor of n then there must be another factor y such that x*y = n, and it's easy to see that x must be smaller than the square root of n.
The second solution requires additional space in the form of an array the size of the number you want to find prime up to, and it's called the Sieve of Eratosthenes, the wikipedia page provides good explanation of this algorithm.
Last edited by nebelung; September 2nd, 2010 at 04:24 PM.
September 2nd, 2010, 06:09 PM

Originally Posted by theburger
Finally, are there any "mistakes" in this code
The obvious mistake is the one that means that it does not compile! How did you test this code? Did you really mean <strings.h>?
As it happens, nothing in your code requires any header other than <stdio.h>. Then it compiles without warnings (VC++ 2008), so that is a good start.
I personally dislike your indentation style since it does not clearly visually pairup opening and cloising braces, but that is a personal issue (unless you are coding in a team and need to conform to project defined coding style).
While on teh subject of style, horizontal and vertical whitespace can be used ot aid readability; don't cram your code, and clearly space your identifiers from your operators.
Having functions with multiple return statements, or a return aywhere other than the last statement is often frowned upon (I am frowning now). The practice is problematic in large and complex functions and for debugging; for example to break when a function returns, you will have to set multiple breakpoints in the function (and make sure you set then for all). For example, you can eliminate the multiple return in is_prime() as follows (Nebelung's improvements notwithstanding):
Code:
int is_prime( int num )
{
int divisor;
for( divisor = 2; divisor <= num / 2 && num % divisor !=0; divisor++)
{
// do nothing
}
return num % divisor != 0;
}
If the return value from scanf() (which you failed to test), is not equaly to the number of format specifiers, it has failed to parse the input stream as requested, and the variable finish will have an undefined value (because it was not initialised or assigned); you should not start the loop in this case.
So long as you realise that this is a very sieve prime algorithm, ok.
September 2nd, 2010, 08:06 PM

you can also check the input whit a simple function like this
Code:
void get_int(int *number){
printf("insert a number: ");
while(scanf("%d", number) != 1){
printf("invalid input!!!\ninsert a new number: ");
while(getchar() != '\n');
}
}
or
Code:
int get_int(void){
int number;
printf("insert a number: ");
while(scanf("%d", &number) != 1){
printf("invalid input!!!\ninsert anew number: ");
while(getchar() != '\n');
}
return number;
}
September 2nd, 2010, 08:46 PM

Originally Posted by nebelung
first Lets look at the following somewhat improved primality testing function:
c Code:
unsigned isPrime (unsigned n) {
if (n == 2)
return 1;
if (n < 2  (n % 2 == 0))
return 0;
for (unsigned i = 3; i*i < n; i += 2)
if (n % i == 0)
return 0;
return 1;
}
One more optimization is in the for loop. The way you have it currently, the compiler has to always do multiplies each time in the for loop, because the terminate condition is i*i < n. Since i is not a constant within the loop, the compiler has to do a multiply each time.
One way to do this is to check this instead:
i < ((unsigned) sqrt(n))
A smart optimizing compiler will note that n stays constant throughout the loop and therefore evaluate sqrt(n) only once in the loop.
If you have a nonoptimizing compiler, you could make sure like this:
Code:
unsigned n_max = (unsigned)sqrt(n);
...
for (unsigned i = 3; i < n_max; i += 2)
Up the Irons
What Would Jimi Do? Smash amps. Burn guitar. Take the groupies home.
"Death Before Dishonour, my Friends!!"  Bruce D ickinson, Iron Maiden Aug 20, 2005 @ OzzFest
Down with Sharon Osbourne
"I wouldn't hire a butcher to fix my car. I also wouldn't hire a marketing firm to build my website."  Nilpo
September 2nd, 2010, 10:12 PM

The major advantage of the Sieve of Eratosthenes algorithm is that it can be a lot faster than approaches which actively test each integer; all it really does is step through the multiples of the primes and marks them off. It's major downside is that is takes a large amount of memory, but with a modern 64bit system with more than 4GB, even this is no hindrance  you can step through the entire 32bit memory range in a matter of minutes, at least in principle. Since I have an older PC with significantly less memory, I intentionally limited the search space to 'only' the first 10,000,000 integers, which it went through in less than 30 seconds.
C Code:
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <stdbool.h>
const int SPACE_SIZE = 10000000;
const int COLUMNS = 6;
int main()
{
unsigned start, end;
int prime_count = 0;
bool digits[SPACE_SIZE];
// set the entire array to a default of 'true'
memset((void *) digits, 1, SPACE_SIZE);
start = clock();
for (int i = 2; i < SPACE_SIZE; i++)
{
// advance to the next value not yet set as composite
while (digits[i] == false)
{
i++;
}
if (i > SPACE_SIZE)
break;
printf("%8d, ", i);
prime_count++;
if ((prime_count % COLUMNS) == 0)
{
printf("\n");
}
// step through the multiples of the current prime
// and mark them off
for (int j = i + i; j < SPACE_SIZE; j += i)
{
digits[j] = false;
}
}
end = clock();
float time_used = (end  start) / (float) CLOCKS_PER_SEC;
printf("\n%d primes found in %.2f sec. compute time\n", prime_count, time_used);
return 0;
}
Feel free to compare this to your program's performance on your own system.
Last edited by ScholRLEA; September 3rd, 2010 at 02:36 PM.
Reason: Added timing and improved formatting to program
September 3rd, 2010, 12:13 AM

There's an old post on the forum (the OP was GTPC, I believe) that uses bits to mark off the numbers. Reduces memory requirements.
Comments on this post
Functionality rules and clarity matters; if you can work a little elegance in there, you're stylin'.
If you can't spell "u", "ur", and "ne1", why would I hire you? 300 baud modem? Forget I mentioned it.
September 3rd, 2010, 12:00 PM

As a response to those of you who replied, thank you for your help.
Regarding the various problems pointed out, I did not think about the scanf checking and returning an integer from main so thanks. I meant to type string.h but I'm not sure why I included this... thanks for pointing that out. Weirdly it compiles fine on my system with gcc. I will try to avoid multiple return statements in future.
Finally the optimization of the algorithm was not really a concern to me at the time. I intend to make it more advanced but right now I'm just worried about writing valid C code than producing a perfect algorithm. I plan to use a slightly different algorithm to the Sieve of Eratosthenes because it has memory inefficiencies (it stores all the numbers including the nonprimes).
Thanks
Angus