So, I've been trying to learn a bit of C, because I'm tired of python being ludicrously slow.
I went around, read bits here and there and learnt enough to recreate something I was messing with recently in python, finding prime numbers. I'm now looking for a bit of critique to see if I'm doing OK or if I'm making a complete and utter mess of this.
#include <stdio.h> /*Need this for "printing" things innit*/
#include <math.h> /*Need this for square rooting*/
/*This function checks a given number for primality, it takes:
- n (integer): the number being tested for primality
- nSqRtIndex (integer): The index of the first prime larger than n's square root in the list of primes
- primes (array): The array of all the primes found (has to at least contain all of the primes before n's square root for the test to work)*/
int checkPrime (int n, int nSqRtIndex, int *primes){
int index = 0;/*This variable will hold the index of the prime currently being checked for divisibility into the number being checked for primality*/
while (index <= nSqRtIndex) { /*While the index being checked for-[blah, see above comment]- is less than the index of the first prime number above the number being checked's square root...*/
if (n % primes[index] == 0) {/*If the number being checked for primality is divisible by the prime at the current index in the list of primes*/
return 0; /*The function stops and returns 0 (for, "False", as in, this number isn't a prime! I found one of its factors! It's a phoney!)*/
}
index++; /*...else, the index variable is incremented by one*/
}
return 1; /*If the function hasn't stopped and returned 0 through testing all of the primes before the square root of the number being tested of primality (fecking mouthful innit), the function returns 1 (for, "True", as in, It's a prime! (not a trap)*/
}
/*main function, this is whoever is reading this.
Whoever is reading this, this is the main function...*/
int main () {
int primesToFind = 519519; /*How many primes the program will find, max seems to be 519519. 519520 ends up in a crash*/
int updateFreq = primesToFind/10; /*This variable holds how frequently an update will be printed (to show how many primes have been found) in primes (e.g. update every 1000 primes found)*/
int primes[primesToFind]; /*This array will hold all the primes*/
primes[0] = 2; /*Adding 2 to the array to begin*/
int primesFound = 1; /*This variable will hold how nmany primes the program has found, starts at one as it's used for the index at which to add a number to the primes array, and the first number (2) is already given to the primes array*/
int n = 3; /*This variable will hold the number currently being checked for primality*/
int nSqRtIndex = 0; /*This vairable will hold the index of the first prime above the current n's square root*/
while (primesFound < primesToFind) {
/*updating nSqRtIndex to point to the first prime above its square root*/
while (sqrt(n) > primes[nSqRtIndex]){ /*...so, while the square root of n (current number) is less than the number in the list of primes at the index that should point to the prime just after the square root of the number*/
nSqRtIndex++; /*One is added to the index at which the first prime above the square root of the number supposedly is*/
}
int isPrime = checkPrime(n, nSqRtIndex, primes); /*The number is tested for primality in the checkPrime function declared above main*/
if (isPrime == 1){ /*If the number is ofund to be prime...*/
primes[primesFound] = n; /*The number's added to the array of primes at the same index as there have been primes found*/
primesFound ++;/*The number of primes found is incremented by one*/
if (primesFound%updateFreq == 0){ /*If the current number of primes found mod the update frequency is equal to 0...*/
printf("Primes found: %d\nLast prime found:%d\n\n", primesFound, primes[primesFound-1]); /*An update is printed including the last prime found, and how many primes have been found*/
}
}
n++; /*The number being checked is incremented by 1*/
}
/*When the integer value of primesToFind primes have been found...*/
printf("Test complete!\nPrimes found: %d\nLast prime found:%d\n\n", primesFound, primes[primesFound-1]); /*A closing statement is printed out*/
return 0;/*main finally returns 0 (supposedly this is to say it works or something, doesn't seem to make a difference to me but whatever)*/
}
If this is all fine and dandy I'll continue getting to grips with this and write the one I have using the Lucas-Lehmer sequence to find Mersenne primes.
I like your clear structure and that you commented so nicely =) Though I would not comment obvious things like n++; or return 0; Comments are great!! but to many might distract from the important ones.
Whether the code is efficient or secure I can't comment anymore; away from the matter for much to long.
I used to comment everything, now while at uni ive been told to only comment two things: Make a list of variables and operands of a method and a short verbal description of the method and thats it.
Yeah, I'm trying to get into the habit of commenting on pretty much everything so even a moron can read it for educational reasons, and so I can get the help of a relative who happens to be a software dev, even though he doesn't know C. Sometimes I just copy pasta from psuedocode too.
Just in general... comment what is needed to understand the code... like imagine you look at it an 5 years; your description of the defined variables I love! but do not overdo it, to much is overwhelming.
In general its good; been out of C(++) for 6 years now.. but I understand your code =D
Groovy gravy, nice to have some judgement from someone that's not a secondary school teacher that only really knows python as well as their class - terribly! Or as aforementioned, like, someone who's into an entirely different language.
A disadvantage to detailed comments is that when you change the code, you need to change the comments to reflect that. Many tools help check correctness of code. No tools check correctness of comments. Inaccurate comments tend to confuse things down the road.
comment only deviations from code patterns and concepts generally used throughout the project.
make sure your variable and function names are self-descriptive, even if they seem long.
document the concepts with diagrams outside the code.
Over commented. Your code should be self-documenting most of the time, comments only needed for certain places, in C it's quite nice to just simply explain the purpose of a function with a comment above like you did. You do not have to do that for main, everybody knows what it does.
Be careful with types... this aint python anymore haha
I removed all your comments and added some feedback in-line
My comments are coming from the perspective of an embedded firmware developer. Efficient C is my game. However, I'm ignoring any optimization of the prime algorithm it'self and focusing strictly on the C code.
#include <stdio.h>
#include <math.h>
#define PRIMES_TO_FIND 519519 // keep magic numbers defined at the top of the document
int checkPrime (int n, int nSqRtIndex, int *primes)
{
int index = 0;
while (index <= nSqRtIndex)
{
if (n % primes[index] == 0) return 0;
index++;
}
return 1;
}
int main ()
{
int updateFreq = PRIMES_TO_FIND/10;
int primes[PRIMES_TO_FIND]; // you cannot dynamically allocate an array this way. Hence, I change the size to a pre-processor defined value.
int primesFound = 0; // it would be cleaner to not hard-code the first prime. The cycles it saves isn't worth the complexity.
int n;
int nSqRtIndex = 0;
for (n = 2; primesFound < PRIMES_TO_FIND; n++) // since you incrament every loop, a for-loop works nicely here
{
float n_sqrt = sqrt(n); // be careful with your types. It was a bit vague what type you were casting "sqrt(n)" into.
while (n_sqrt > primes[nSqRtIndex]) nSqRtIndex++;
if (checkPrime(n, nSqRtIndex, primes) == 1)
{
primes[primesFound] = n;
primesFound ++;
if (primesFound % updateFreq == 0)
{
printf("Primes found: %d\nLast prime found:%d\n\n", primesFound, primes[primesFound-1]);
}
}
}
printf("Test complete!\nPrimes found: %d\nLast prime found:%d\n\n", primesFound, primes[primesFound-1]);
return 0;
}
sorry... the tab on that last return doesn't display correctly.
It can be done but you need to set -std=c99 unless your compiler defaults to C99. Support for variable length arrays is mandatory in C99, but C11 makes it optional, i.e. not guaranteed to work (more info: https://en.wikipedia.org/wiki/Variable-length_array ).
lol, how do I decide what the "magic numbers" are though? I could just define the primes array, n, and nSqRtIndex at the top of the document and never have to pass them into the checkPrime function.
Just static variables I guess? In which case, why isn't updateFreq up there?
About the array shizzle, worked fine when I compiled it. shrugs, using Dev C++
not all compilers are friendly with dynamic alloc method.
The title said "C" not "C++" so that's what I was going off of.
Magic numbers are when you have a specific configuration like "519519". It's not a good idea to have it down in your code because it will get buried and be difficult to find or know what it is when you want to come back some time later to change it. It's not an issue with small hobby projects... but trust me... when you start working on big code basses on the job, these kind of practices are MANDATORY.
"updateFreq" is technically a magic number but it's much less important since it's just for a printf. I didn't bother.
It's how often an update is printed for how many primes have been found. I set it to just be a tenth of the amount of primes being found. It's something that might want to be changed often if I can find out why it won't let me find more than 519519 primes!
Which reminds me, any idea why I can't ask it for more than 519519 primes? If I change it to even 519520, this happens...
For as long as your program is made of only a few functions and one file, feel free to use static and play around with the thought of what can be static (learning by reasoning and hands-on experience). When you start to span a couple of files (your function becomes called from another file), or your project becomes more complex in other ways, you will want to pass the pointer, instead of using static - by doing so, you separate the concerns of memory management from the algorithm that will be operating on the said memory. This will make your functions more reusable in the long run. For example, a couple of program versions later, you could be reading the magic value from a command line parameter. Then you would probably allocate memory on heap, not on stack, to avoid overflowing the stack...
Stack overflow. EDIT: time to learn malloc and free :) . EDIT EDIT: or use a static array. EDIT EDIT EDIT: @eidolonFIRE might be more right here than I am. Could be integer out of range too.
Oh, I was sad when they stopped developing it. Perfect entry-level, when you just want to write some code, and no need to think about the setup.
since you say you may want to change the printf frequency later, then definitely make it a #define at the top of the document.
The crash could be because you are using 32bit integers. Python has no limit to the "bit depth" of a variable but in C you have real memory types. An "int" (which is typically a long int) can only have a range of [−2147483647, +2147483647]. Most likely you are reaching a point when your integer is wrapping around to a negative number and one of your ">" while statements is put into an infinite spin. Your OS detects this after a bit of time and halts the program.
