{"id":598,"date":"2024-06-21T09:00:00","date_gmt":"2024-06-21T01:00:00","guid":{"rendered":"https:\/\/seanxd.com\/?p=598"},"modified":"2024-06-25T16:55:53","modified_gmt":"2024-06-25T08:55:53","slug":"zerojudge-d120","status":"publish","type":"post","link":"https:\/\/seanxd.com\/en\/zerojudge-d120\/","title":{"rendered":"ZeroJudge D120: Count the factors"},"content":{"rendered":"

UVa 10699 \u2013 Count the factors<\/h4>\n\n\n\n

Write a program to calculate how many distinct prime factors a positive integer has. For example, 45 = 33<\/em>5, so 45 has 2 prime factors (3 and 5).<\/p>\n\n\n\n

Sample Inputs\/Outputs<\/h2>\n\n\n\n
Sample Input(s)<\/th>Sample Output(s)<\/th><\/tr><\/thead>
Each set of test data is in a single line containing a positive integer N (1 < N \u2264 1000000).
If N = 0, it means the input has ended.<\/td>		For each set of test data, output a line indicating the number of distinct prime factors of N. Please refer to the sample output for the output format.<\/td><\/tr>
7
8
45
289384
930887
692778
636916
747794
238336
885387
760493
516650
641422
0<\/td>		7 : 1
8 : 1
45 : 2
289384 : 3
930887 : 2
692778 : 5
636916 : 4
747794 : 3
238336 : 3
885387 : 2
760493 : 2
516650 : 3
641422 : 3<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

Thought Process<\/h2>\n\n\n\n

You can create a function to determine whether a number is prime. Use a for loop from 2 to N. If you find a factor of N, check if it's a prime number. If it's prime, increment the answer by 1.<\/p>\n\n\n\n

Sample Code\uff0dZeroJudge D120: Count the factors<\/a><\/h3>\n\n\n\n
#include <iostream>\n#include <math.h>\nusing namespace std;\n\nbool isPrime(int N) {\n    for (int i = 2; i<int(sqrt(N)+1); i++) {\n        if (N % i == 0) return false;\n    }\n    return true;\n}\n\nint main() {\n    cin.sync_with_stdio(0);\n    cin.tie(0);\n    int N;\n    while (cin >> N && N != 0) {\n        int ans = 0;\n        for (int i = 2; i<=N; i++) {\n            if (N % i == 0 && isPrime(i)) {\n                ans++;\n            }\n        }\n        cout << N << " : " << ans << "\\n";\n    }\n}\n\n\/\/ZeroJudge D120\n\/\/Dr. SeanXD<\/code><\/pre><\/div>","protected":false},"excerpt":{"rendered":"
\u540c\u984c\uff1aUVa 10699 – Count the factors \u5beb\u4e00\u500b\u7a0b\u5f0f\u7b97\u51fa\u4e00\u500b\u6b63\u6574\u6578\u6709\u591a\u5c11\u500b […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"nf_dc_page":"","footnotes":""},"categories":[18],"tags":[8,34,13,9],"class_list":["post-598","post","type-post","status-publish","format-standard","hentry","category-uva","tag-8","tag-34","tag-13","tag-9"],"blocksy_meta":[],"_links":{"self":[{"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/posts\/598","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/comments?post=598"}],"version-history":[{"count":2,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/posts\/598\/revisions"}],"predecessor-version":[{"id":991,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/posts\/598\/revisions\/991"}],"wp:attachment":[{"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/media?parent=598"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/categories?post=598"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/tags?post=598"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}