{"id":4433,"date":"2020-11-07T00:01:49","date_gmt":"2020-11-07T08:01:49","guid":{"rendered":"https:\/\/c-for-dummies.com\/blog\/?p=4433"},"modified":"2020-11-07T07:39:09","modified_gmt":"2020-11-07T15:39:09","slug":"more-efficient-prime-number-calculations","status":"publish","type":"post","link":"https:\/\/c-for-dummies.com\/blog\/?p=4433","title":{"rendered":"More Efficient Prime Number Calculations"},"content":{"rendered":"

A long time ago, I looked at one of my prime number hunting programs, such as the one demonstrated in last week’s Lesson<\/a>. I thought, “How can I make this program more efficient?” It’s something all programmers should do.
\n
\nFirst I figured that only prime numbers themselves matter in the prime number hunt.<\/p>\n

For example, if you have the value n<\/em>, you can check to see whether it’s divisible by all the values 2 through n<\/em> or you can just check to see whether it’s divisible by prime numbers from 2 to n<\/em>. After all, the in-between values such as 4, 10, 15, and so on already have prime number factors. So these values can be merrily skipped as you check for factors of n<\/em>.<\/p>\n

Further, you don’t really need to check for factors greater than n<\/em>\/2. These larger factors probably don’t divide cleanly into n<\/em> anyhow, so why bother doing the math? In fact, I’m sure there’s some mathematical theory on what fraction of a number can contain the largest factor of that number. At some point, checking lager values is a waste of time.<\/p>\n

I’m no mathematician. In fact, what kept me from computers in college was a fear of math; I’m terrible at it. My university math grades are horrid. Yet, I enjoy ruminating on the topic, which is what got me going with this prime number hunt code:<\/p>\n

2020_11_07-Lesson.c<\/a><\/h3>\n
\r\n#include <stdio.h>\r\n\r\n#define COUNT 100\r\n#define TRUE 1\r\n#define FALSE 0\r\n\r\nint main(void)\r\n{\r\n    int n,i,c,a,index,isprime;\r\n    int primes[COUNT];\r\n    \r\n    printf(\"The first %d primes:\\n\\n\",COUNT);\r\n\r\n\/* initialize *\/<\/span>\r\n    index = 0;                        \/* set index for array *\/<\/span>\r\n    primes[index] = 2;                \/* 2 is the first prime *\/<\/span>\r\n    a = 1;                            \/* set counter *\/<\/span>\r\n\r\n\/* calculate the first COUNT prime numbers *\/<\/span>\r\n    while(index<COUNT)\r\n    {\r\n        n = primes[index] + a;        \/* next value after last prime *\/<\/span>\r\n                                      \/* is n prime? *\/<\/span>\r\n        isprime=TRUE;                 \/* Assume it is prime for now *\/<\/span>\r\n\r\n        for(i=0;i<index;i++)          \/* divide n by recorded primes *\/<\/span>\r\n        {\r\n            c = n\/primes[i];\r\n            if(n == primes[i]*c)      \/* if TRUE, n is not prime *\/<\/span>\r\n            {\r\n                isprime=FALSE;\r\n                break;                \/* this saves time *\/<\/span>\r\n            }\r\n            if(primes[i] > (n>>1))    \/* eliminate divisors *\/<\/span>\r\n                break;                \/* greater than n\/2 *\/<\/span>\r\n        }\r\n\r\n        if(isprime)                   \/* the value is prime *\/<\/span>\r\n        {\r\n            index++;\r\n            primes[index] = n;        \/* add it to the array *\/<\/span>\r\n            a = 1;                    \/* set to next number *\/<\/span>\r\n        }\r\n        else\r\n            a++;                      \/* jump to text next value *\/<\/span>\r\n                                      \/* the value of a indicates the\r\n                                         space between primes. It will\r\n                                         never be <2 but can get quite\r\n                                         large *\/<\/span>\r\n    }\r\n\r\n\/* display the results *\/<\/span>\r\n    for(i=0;i<COUNT;i++)\r\n        printf(\"%5d\\t\",primes[i]);\r\n    printf(\"\\n\\n\");\r\n\r\n    return 0;\r\n}<\/pre>\n
Unlike last week’s examples, this code tracks found prime numbers in in an array, primes[]<\/code> declared at Line 10. It’s initialized with value 2 at the zeroth element (Line 16), which saves time with other calculations.<\/p>\n
In the while<\/em> loop, potential prime values are stored in variable n<\/code>. This value is initialized to the next integer after the previously-stored prime number at Line 22: n = primes[index]+a<\/code>. This choice saves time over starting each new hunt at a lower number.<\/p>\n
Next, the program runs a for<\/em> loop that divides n<\/code> by values stored in the primes[]<\/code> array at Line 28. Tests are made to determine whether the value is cleanly divisible. If so, the number isn’t prime and the for<\/em> loop breaks.<\/p>\n
Found primes are added to the array at Line 41.<\/p>\n
The code hunts for the first 100 primes, which are output:<\/p>\n
The first 100 primes:<\/p>\n
    2\t    3\t    5\t    7\t   11\t   13\t   17\t   19\t   23\t   29\t   31\t   37\t   41\t   43\t   47\t   53\t   59\t   61\t   67\t   71\t   73\t   79\t   83\t   89\t   97\t  101\t  103\t  107\t  109\t  113\t  127\t  131\t  137\t  139\t  149\t  151\t  157\t  163\t  167\t  173\t  179\t  181\t  191\t  193\t  197\t  199\t  211\t  223\t  227\t  229\t  233\t  239\t  241\t  251\t  257\t  263\t  269\t  271\t  277\t  281\t  283\t  293\t  307\t  311\t  313\t  317\t  331\t  337\t  347\t  349\t  353\t  359\t  367\t  373\t  379\t  383\t  389\t  397\t  401\t  409\t  419\t  421\t  431\t  433\t  439\t  443\t  449\t  457\t  461\t  463\t  467\t  479\t  487\t  491\t  499\t  503\t  509\t  521\t  523\t  541<\/code><\/p>\n
You can modify the code to output a greater span of prime numbers: Change the defined constant COUNT<\/code> to something larger. Unlike my other examples, this code runs a lot faster because it’s not churning through every value from 2 to n<\/code> for each cycle.<\/p>\n
I know plenty of other prime number hunting programs are possible. Perhaps you can venture out and write a unique one on your own. Doing so is great coding practice.<\/p>\n","protected":false},"excerpt":{"rendered":"
My shortcut for hunting for prime numbers. Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[],"class_list":["post-4433","post","type-post","status-publish","format-standard","hentry","category-main"],"_links":{"self":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/4433","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=4433"}],"version-history":[{"count":6,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/4433\/revisions"}],"predecessor-version":[{"id":4458,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/4433\/revisions\/4458"}],"wp:attachment":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=4433"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=4433"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=4433"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}