首页 > 代码库 > SGU - 102 - Coprimes （简单数论！）
SGU - 102 - Coprimes （简单数论！）
SGU - 102
Coprimes
| Time Limit: 250MS | Memory Limit: 4096KB | 64bit IO Format: %I64d & %I64u |
Description
For given integer N (1<=N<=104) find amount of positive numbers not greater than N that coprime with N. Let us call two positive integers (say, A and B, for example) coprime if (and only if) their greatest common divisor is 1. (i.e. A and B are coprime iff gcd(A,B) = 1).
Input
Input file contains integer N.
Output
Write answer in output file.
Sample Input
9
Sample Output
6
Source
简单数论题！
AC代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
const int maxn = 10005;
int flag[maxn];
int main()
{
int n;
scanf("%d", &n);
memset(flag, 0, sizeof(flag));
int m = n;
for(int i=2; i<=m; i++) //没加=号，WA了一次
{
if(m%i==0)
{
for(int j = i; j<=n; j+=i)
{
flag[j] = 1;
}
while(m%i==0)
{
m/=i;
}
}
}
int ans = 0;
for(int i=1; i<=n; i++)
{
if(flag[i]==0)ans++;
}
printf("%d\n", ans);
return 0;
} SGU - 102 - Coprimes （简单数论！）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。