若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。


  • 运维

  • 前端

  • 编程

  • 随笔

  • hust-oj

1134: Problem E: Relatives

发表于 2017-10-06   |   分类于 HUSTOJ   |   阅读次数 1,321

题目描述

Problem E: Relatives
Given n, a positive integer, how many positive integers less than n are relatively prime to n? Two integers a and b are relatively prime if there are no integers x > 1, y > 0, z > 0 such that a = xy and b = xz.
There are several test cases. For each test case, standard input contains a line with n <= 1,000,000,000. A line containing 0 follows the last case.
For each test case there should be single line of output answering the question posed above.

输入

暂无

输出

暂无

样例输入

7
12
0

样例输出

6
4

参考代码

#include <stdio.h>
main() 
{
    int n,i,sum;
    while (1 == scanf("%d",&n) && n) 
    {
        sum = n;
        for (i=2;i*i <= n;i++) 
        {
            if (n%i == 0) 
            {
                sum -= sum/i;
            }
            while (n%i == 0) n /= i;
        }
        if (n > 1) sum -= sum/n;
        printf("%dn",sum);
   }
}

解析

暂无

hustoj

发表评论 取消回复

邮箱地址不会被公开。 必填项已用*标注

*
*


hoxis wechat
著作权归作者所有
站点更新说明
  • 文章目录
  • 站点概览
若是凉夜已成梦

若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。

1904 日志
6 分类
12 标签
RSS
weibo github twitter facebook

友情链接

Skip 原站点 Dreams孤独患者
© 2017 若是凉夜已成梦
Powered by WordPress | 已运行
Theme By NexT.Mist