{"id":4419,"date":"2020-10-31T00:01:06","date_gmt":"2020-10-31T07:01:06","guid":{"rendered":"https:\/\/c-for-dummies.com\/blog\/?p=4419"},"modified":"2020-10-31T09:01:41","modified_gmt":"2020-10-31T16:01:41","slug":"generating-prime-numbers","status":"publish","type":"post","link":"https:\/\/c-for-dummies.com\/blog\/?p=4419","title":{"rendered":"Generating Prime Numbers"},"content":{"rendered":"

Numbers with only two factors, one and themselves, are prime. One way to discover which numbers are prime in a computer program is to plow through all the factors.
\n
\nIn last week’s Lesson<\/a>, I presented code that counts the number of factors for a range of values. When the number of factors is zero (excluding 1 and the value itself), the value is prime. The following code makes an improvement to the examples from last week’s Lesson by adding a TRUE<\/code>\/FALSE<\/code> (Boolean) variable isprime<\/code> to determine prime numbers:<\/p>\n

2020_10_31-Lesson-a.c<\/a><\/h3>\n
\r\n#include <stdio.h>\r\n\r\n#define TRUE 1\r\n#define FALSE 0\r\n\r\nint main()\r\n{\r\n    int prime,x,isprime;\r\n\r\n    prime = 2;\r\n    while(prime<100)\r\n    {\r\n        isprime = TRUE;\r\n        printf(\"%d:\",prime);\r\n        for( x=2; x<prime; x++ )\r\n        {\r\n            if( prime%x == 0 )\r\n            {\r\n                isprime=FALSE;\r\n                break;\r\n            }\r\n        }\r\n\r\n        if( isprime )\r\n            puts(\"Prime\");\r\n        else\r\n            puts(\"Not prime\");\r\n\r\n        prime++;\r\n    }\r\n\r\n    return(0);\r\n}<\/pre>\n
Variable isprime<\/code> is declared as an int<\/em>, not a _bool<\/em>, still its use is the same. The variable is initialized to TRUE<\/code> at Line 13. Line 17 tests for factors:<\/p>\n
if( prime%x == 0 )<\/code>)<\/p>\n
If the result of prime%x<\/code> is equal to zero, a factor has been found and the value of isprime<\/code> is set to FALSE<\/code>, then the loop breaks (Line 20). But when a value stored in variable prime<\/code> lacks factors, isprime<\/code> remains TRUE<\/code> and an if-else<\/em> structure outputs the proper results, shown here:<\/p>\n
2:Prime
\n3:Prime
\n4:Not prime
\n5:Prime
\n6:Not prime
\n7:Prime
\n8:Not prime
\n9:Not prime
\n10:Not prime
\n11:Prime<\/p>\n
... continues<\/em> ...<\/p>\n
88:Not prime
\n89:Prime
\n90:Not prime
\n91:Not prime
\n92:Not prime
\n93:Not prime
\n94:Not prime
\n95:Not prime
\n96:Not prime
\n97:Prime
\n98:Not prime
\n99:Not prime<\/code><\/p>\n
Of course, this list is difficult to sift through. It’s more of a subtle update to the code from last week’s Lesson. In the following update, the code outputs only found prime numbers:<\/p>\n
2020_10_31-Lesson-b.c<\/a><\/h3>\n
\r\n#include <stdio.h>\r\n\r\n#define TRUE 1\r\n#define FALSE 0\r\n\r\nint main()\r\n{\r\n    int prime,x,isprime;\r\n\r\n    prime = 2;\r\n    while(prime<100)\r\n    {\r\n        isprime = TRUE;\r\n        for( x=2; x<prime; x++ )\r\n        {\r\n            if( prime%x == 0 )\r\n            {\r\n                isprime=FALSE;\r\n                break;\r\n            }\r\n        }\r\n\r\n        if( isprime )\r\n            printf(\" %d\",prime);\r\n\r\n        prime++;\r\n    }\r\n    putchar('\\n');\r\n\r\n    return(0);\r\n}<\/pre>\n
The code limits output to a single printf()<\/em> statement at Line 24, showing only prime numbers from 2 through 99:<\/p>\n
 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97<\/code><\/p>\n
I’m sure the output appeared immediately on your computer; the code doesn’t really work hard to pump out the first several prime numbers. For a thrill, change the looping value at Line 11 to 1000000 (one million) and see how long those last few values take to output.<\/p>\n
This code is just one way to hunt prime numbers. In next week’s Lesson I show a different approach, one that is optimized slightly.<\/p>\n","protected":false},"excerpt":{"rendered":"
One way of coding a prime number generating program is to discover which numbers have factors of only 1 and themselves. 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-4419","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\/4419","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=4419"}],"version-history":[{"count":6,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/4419\/revisions"}],"predecessor-version":[{"id":4438,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/4419\/revisions\/4438"}],"wp:attachment":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=4419"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=4419"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=4419"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}