C++ Coding Test Course, Euler's Pi - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/atmokpo.com\/w\/34262\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"C++ Coding Test Course, Euler's Pi - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"Hello! In this tutorial, we will learn how to solve the Euler’s Totient Function problem using C++. This problem involves finding the count of integers that are coprime to a given integer n, which are less than or equal to n. What is the Euler’s Totient Function? The Euler’s Totient Function \u03c6(n) is a function … \ub354 \ubcf4\uae30 "C++ Coding Test Course, Euler’s Pi"\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/34262\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:26:10+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T10:57:56+00:00\" \/>\n<meta name=\"author\" content=\"root\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:site\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:label1\" content=\"\uae00\uc4f4\uc774\" \/>\n\t<meta name=\"twitter:data1\" content=\"root\" \/>\n\t<meta name=\"twitter:label2\" content=\"\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04\" \/>\n\t<meta name=\"twitter:data2\" content=\"2\ubd84\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/atmokpo.com\/w\/34262\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34262\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"C++ Coding Test Course, Euler’s Pi\",\"datePublished\":\"2024-11-01T09:26:10+00:00\",\"dateModified\":\"2024-11-01T10:57:56+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34262\/\"},\"wordCount\":388,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"C++ Coding Test Tutorials\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/34262\/\",\"url\":\"https:\/\/atmokpo.com\/w\/34262\/\",\"name\":\"C++ Coding Test Course, Euler's Pi - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:26:10+00:00\",\"dateModified\":\"2024-11-01T10:57:56+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34262\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/34262\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/34262\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"C++ Coding Test Course, Euler’s Pi\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/atmokpo.com\/w\/#website\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"description\":\"\",\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/atmokpo.com\/w\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"ko-KR\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"contentUrl\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"width\":400,\"height\":400,\"caption\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\"},\"image\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/x.com\/bebubo4\"]},{\"@type\":\"Person\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\",\"name\":\"root\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"caption\":\"root\"},\"sameAs\":[\"http:\/\/atmokpo.com\/w\"],\"url\":\"https:\/\/atmokpo.com\/w\/author\/root\/\"}]}<\/script>\n","yoast_head_json":{"title":"C++ Coding Test Course, Euler's Pi - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/atmokpo.com\/w\/34262\/","og_locale":"ko_KR","og_type":"article","og_title":"C++ Coding Test Course, Euler's Pi - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"Hello! In this tutorial, we will learn how to solve the Euler’s Totient Function problem using C++. This problem involves finding the count of integers that are coprime to a given integer n, which are less than or equal to n. What is the Euler’s Totient Function? The Euler’s Totient Function \u03c6(n) is a function … \ub354 \ubcf4\uae30 \"C++ Coding Test Course, Euler’s Pi\"","og_url":"https:\/\/atmokpo.com\/w\/34262\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:26:10+00:00","article_modified_time":"2024-11-01T10:57:56+00:00","author":"root","twitter_card":"summary_large_image","twitter_creator":"@bebubo4","twitter_site":"@bebubo4","twitter_misc":{"\uae00\uc4f4\uc774":"root","\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04":"2\ubd84"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/atmokpo.com\/w\/34262\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/34262\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"C++ Coding Test Course, Euler’s Pi","datePublished":"2024-11-01T09:26:10+00:00","dateModified":"2024-11-01T10:57:56+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/34262\/"},"wordCount":388,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["C++ Coding Test Tutorials"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/34262\/","url":"https:\/\/atmokpo.com\/w\/34262\/","name":"C++ Coding Test Course, Euler's Pi - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:26:10+00:00","dateModified":"2024-11-01T10:57:56+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/34262\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/34262\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/34262\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"C++ Coding Test Course, Euler’s Pi"}]},{"@type":"WebSite","@id":"https:\/\/atmokpo.com\/w\/#website","url":"https:\/\/atmokpo.com\/w\/","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","description":"","publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/atmokpo.com\/w\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"ko-KR"},{"@type":"Organization","@id":"https:\/\/atmokpo.com\/w\/#organization","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","url":"https:\/\/atmokpo.com\/w\/","logo":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/","url":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","contentUrl":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","width":400,"height":400,"caption":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8"},"image":{"@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/x.com\/bebubo4"]},{"@type":"Person","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7","name":"root","image":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","caption":"root"},"sameAs":["http:\/\/atmokpo.com\/w"],"url":"https:\/\/atmokpo.com\/w\/author\/root\/"}]}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34262","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/comments?post=34262"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34262\/revisions"}],"predecessor-version":[{"id":34263,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34262\/revisions\/34263"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=34262"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=34262"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=34262"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}

{"id":34262,"date":"2024-11-01T09:26:10","date_gmt":"2024-11-01T09:26:10","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34262"},"modified":"2024-11-01T10:57:56","modified_gmt":"2024-11-01T10:57:56","slug":"c-coding-test-course-eulers-pi-2","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34262\/","title":{"rendered":"C++ Coding Test Course, Euler’s Pi"},"content":{"rendered":"

<\/p>\n

Hello! In this tutorial, we will learn how to solve the Euler’s Totient Function problem using C++. This problem involves finding the count of integers that are coprime to a given integer n, which are less than or equal to n.<\/p>\n

What is the Euler’s Totient Function?<\/h2>\n

The Euler’s Totient Function \u03c6(n) is a function that represents the count of integers that are coprime to the number n. For example:<\/p>\n

\u03c6(1) = 1 (1 is always coprime with itself)<\/li>\n
\u03c6(2) = 1 (The only number less than 2 that is coprime with 2 is 1)<\/li>\n
\u03c6(3) = 2 (1 and 2 are coprime with 3)<\/li>\n
\u03c6(4) = 2 (1 and 3 are coprime with 4)<\/li>\n

\u03c6(5) = 4 (1, 2, 3, 4 are coprime with 5)<\/li>\n<\/ul>\n

Problem Description<\/h2>\n
Write an algorithm to calculate the value of \u03c6(n) for a given n. The input will be an integer n (1 \u2264 n \u2264 10^{6<\/sup>).<\/p>\n}

Example Input<\/h3>\n

10<\/code><\/pre>\nExample Output<\/h3>\n4<\/code><\/pre>\nExplanation: 1, 3, 7, and 9 are coprime with 10.<\/p>\n
Steps to Solve the Problem<\/h2>\n
Step 1: Understand the Properties<\/h3>\nThe value of the Euler’s Totient Function has the following properties:<\/p>\n
\nIf p is a prime number, then \u03c6(p) = p – 1<\/li>\n
If p is a prime number, then \u03c6(p^{k<\/sup>) = p^{k<\/sup> – p^{k-1<\/sup> = p^{k<\/sup>(1 – 1\/p)<\/li>\n}}}}
If two primes p and q are coprime, then \u03c6(p*q) = \u03c6(p) * \u03c6(q)<\/li>\n<\/ul>\nStep 2: Use the Sieve of Eratosthenes for Range Calculation<\/h3>\nTo find the Euler’s Totient values for all numbers up to n, we can utilize the Sieve of Eratosthenes method to find composite numbers and calculate the totient values. This method operates with a time complexity of O(n log log n).<\/p>\n
Step 3: Implement the Algorithm<\/h3>\nHere is an implementation in C++ for calculating the Euler’s Totient Function:<\/p>\n
\n#include <iostream>\n#include <vector>\n\nusing namespace std;\n\nvoid eulerTotient(int n, vector<int>& phi) {\n    for (int i = 0; i <= n; i++) {\n        phi[i] = i; \/\/ initialize phi\n    }\n    for (int i = 2; i <= n; i++) {\n        if (phi[i] == i) { \/\/ if i is prime\n            for (int j = i; j <= n; j += i) {\n                phi[j] *= (i - 1); \/\/ multiply by (1 - 1\/p) since prime p is included\n                phi[j] \/= i;\n            }\n        }\n    }\n}\n\nint main() {\n    int n;\n    cout << \"Please enter the value of n: \";\n    cin >> n;\n\n    vector<int> phi(n + 1);\n    eulerTotient(n, phi);\n\n    cout << \"\u03c6(\" << n << \") = \" << phi[n] << endl;\n    return 0;\n}\n    <\/code><\/pre>\nStep 4: Explanation of the Code<\/h3>\nIn the above code:<\/p>\n
\nFirst, we initialize \u03c6[i] for each number.<\/li>\n
Next, we find the prime i and update \u03c6[j] for all multiples j.<\/li>\n
Finally, the Euler’s Totient value for n is stored in \u03c6[n].<\/li>\n<\/ul>\nStep 5: Performance Improvement<\/h3>\nThis algorithm has a performance of O(n log log n), which works efficiently even for the maximum range of 10^{6<\/sup>.<\/p>\n}
Conclusion<\/h2>\nIn this tutorial, we covered how to efficiently calculate the Euler’s Totient Function using C++. The method utilizing the Sieve of Eratosthenes is fast and useful, and it can also be beneficial for coding tests. Keep studying various algorithms to enhance your coding skills!<\/p>\n
References<\/h2>\n\nEuler’s Totient Function – Wikipedia<\/a><\/li>\n
GeeksforGeeks – Euler’s Totient Function<\/a><\/li>\n<\/ul>\n<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"Hello! In this tutorial, we will learn how to solve the Euler’s Totient Function problem using C++. This problem involves finding the count of integers that are coprime to a given integer n, which are less than or equal to n. What is the Euler’s Totient Function? The Euler’s Totient Function \u03c6(n) is a function … \ub354 \ubcf4\uae30 “C++ Coding Test Course, Euler’s Pi”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[111],"tags":[],"class_list":["post-34262","post","type-post","status-publish","format-standard","hentry","category-c-coding-test-tutorials-2"],"yoast_head":"\nC++ Coding Test Course, Euler's Pi - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/atmokpo.com\/w\/34262\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"C++ Coding Test Course, Euler's Pi - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"Hello! In this tutorial, we will learn how to solve the Euler’s Totient Function problem using C++. This problem involves finding the count of integers that are coprime to a given integer n, which are less than or equal to n. What is the Euler’s Totient Function? The Euler’s Totient Function \u03c6(n) is a function … \ub354 \ubcf4\uae30 "C++ Coding Test Course, Euler’s Pi"\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/34262\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:26:10+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T10:57:56+00:00\" \/>\n<meta name=\"author\" content=\"root\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:site\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:label1\" content=\"\uae00\uc4f4\uc774\" \/>\n\t<meta name=\"twitter:data1\" content=\"root\" \/>\n\t<meta name=\"twitter:label2\" content=\"\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04\" \/>\n\t<meta name=\"twitter:data2\" content=\"2\ubd84\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/atmokpo.com\/w\/34262\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34262\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"C++ Coding Test Course, Euler’s Pi\",\"datePublished\":\"2024-11-01T09:26:10+00:00\",\"dateModified\":\"2024-11-01T10:57:56+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34262\/\"},\"wordCount\":388,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"C++ Coding Test Tutorials\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/34262\/\",\"url\":\"https:\/\/atmokpo.com\/w\/34262\/\",\"name\":\"C++ Coding Test Course, Euler's Pi - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:26:10+00:00\",\"dateModified\":\"2024-11-01T10:57:56+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34262\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/34262\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/34262\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"C++ Coding Test Course, Euler’s Pi\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/atmokpo.com\/w\/#website\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"description\":\"\",\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/atmokpo.com\/w\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"ko-KR\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"contentUrl\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"width\":400,\"height\":400,\"caption\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\"},\"image\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/x.com\/bebubo4\"]},{\"@type\":\"Person\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\",\"name\":\"root\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"caption\":\"root\"},\"sameAs\":[\"http:\/\/atmokpo.com\/w\"],\"url\":\"https:\/\/atmokpo.com\/w\/author\/root\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"C++ Coding Test Course, Euler's Pi - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/atmokpo.com\/w\/34262\/","og_locale":"ko_KR","og_type":"article","og_title":"C++ Coding Test Course, Euler's Pi - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"Hello! In this tutorial, we will learn how to solve the Euler’s Totient Function problem using C++. This problem involves finding the count of integers that are coprime to a given integer n, which are less than or equal to n. What is the Euler’s Totient Function? The Euler’s Totient Function \u03c6(n) is a function … \ub354 \ubcf4\uae30 \"C++ Coding Test Course, Euler’s Pi\"","og_url":"https:\/\/atmokpo.com\/w\/34262\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:26:10+00:00","article_modified_time":"2024-11-01T10:57:56+00:00","author":"root","twitter_card":"summary_large_image","twitter_creator":"@bebubo4","twitter_site":"@bebubo4","twitter_misc":{"\uae00\uc4f4\uc774":"root","\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04":"2\ubd84"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/atmokpo.com\/w\/34262\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/34262\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"C++ Coding Test Course, Euler’s Pi","datePublished":"2024-11-01T09:26:10+00:00","dateModified":"2024-11-01T10:57:56+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/34262\/"},"wordCount":388,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["C++ Coding Test Tutorials"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/34262\/","url":"https:\/\/atmokpo.com\/w\/34262\/","name":"C++ Coding Test Course, Euler's Pi - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:26:10+00:00","dateModified":"2024-11-01T10:57:56+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/34262\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/34262\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/34262\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"C++ Coding Test Course, Euler’s Pi"}]},{"@type":"WebSite","@id":"https:\/\/atmokpo.com\/w\/#website","url":"https:\/\/atmokpo.com\/w\/","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","description":"","publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/atmokpo.com\/w\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"ko-KR"},{"@type":"Organization","@id":"https:\/\/atmokpo.com\/w\/#organization","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","url":"https:\/\/atmokpo.com\/w\/","logo":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/","url":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","contentUrl":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","width":400,"height":400,"caption":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8"},"image":{"@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/x.com\/bebubo4"]},{"@type":"Person","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7","name":"root","image":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","caption":"root"},"sameAs":["http:\/\/atmokpo.com\/w"],"url":"https:\/\/atmokpo.com\/w\/author\/root\/"}]}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34262","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/comments?post=34262"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34262\/revisions"}],"predecessor-version":[{"id":34263,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34262\/revisions\/34263"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=34262"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=34262"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=34262"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}

Problem Description<\/h2>\nWrite an algorithm to calculate the value of \u03c6(n) for a given n. The input will be an integer n (1 \u2264 n \u2264 106<\/sup>).<\/p>\n

Steps to Solve the Problem<\/h2>\n

Step 5: Performance Improvement<\/h3>\nThis algorithm has a performance of O(n log log n), which works efficiently even for the maximum range of 106<\/sup>.<\/p>\n

Problem Description<\/h2>\n
Write an algorithm to calculate the value of \u03c6(n) for a given n. The input will be an integer n (1 \u2264 n \u2264 10^{6<\/sup>).<\/p>\n}

Step 5: Performance Improvement<\/h3>\n
This algorithm has a performance of O(n log log n), which works efficiently even for the maximum range of 10^{6<\/sup>.<\/p>\n}