初级光能
已知整数x, y,求区间[x, y)内，有多少个数是质数。
输入描述 Input Description
两个数用空格隔开，分别表示x, y。
输出描述 Output Description
一个数，表示质数的个数
样例输入 Sample Input
22 37
样例输出 Sample Output
3
王学庚在2018-07-15 08:50:23追加了内容
#include<iostream>
#include<cstdio>
#include<iomanip>
using namespace std;
long long int a,m,n,i,j;
int main()
{
cin>>n>>m;
for(i=n;i<=m;i++)
{
for(j=2;j<i;j++)
{
if(i%j==0)
{
a++;
break;
}
}
}
cout<<(m-n)-a<<endl;
return 0;
}
#include<iostream>
#include<cstdio>
#include<iomanip>
using namespace std;
long long int a,m,n,i,j;
int main()
{
cin>>n>>m;
for(i=n;i<=m;i++)
{
for(j=2;j<i;j++)
{
if(i%j==0)
{
a++;
break;
}
}
}
cout<<(m-n)-a<<endl;
return 0;
}
修练者
题目是让求i从1增加到n的gcd(n,i)的和，我们假设gcd(n,i) = k，则gcd(n/k,i/k) = 1。即假设gcd(n/k, x ) = 1，则gcd(n,x*k) = k。gcd(n,i) = k,k的取值是确定的，即n的所有因子，所以，满足gcd(n/k,x) = 1个x的个数乘以k即为所有满足gcd(n,i) = k 的和。因此就转化为n/k的欧拉函数的值乘以k的所有的和。
举个例子12来说，12的因子为1，2，3，4，6，12，则和为12/1的欧拉函数值*1 + 12/2的欧拉函数值 * 2 + 12/3的欧拉函数值 * 3 + 12/4的欧拉函数值 * 4 + 12/6的欧拉函数值*6 + 12/12 的欧拉函数值 * 12。
至于一个数n的所有因子，可以先将n分解成素数幂的形式，然后再用排列组合的知识或者是深搜求出其所有因子。
1590互质数
时梓繁在2018-07-17 14:57:14追加了内容
应是：
首先，区间[x,y)表示的是>=x且<y，你的理解有问题。
然后，中间的判断素数，如果找到因数了，就应该直接退出当前循环（break），可以节省时间。
但是就是这样也只有40分（TLE，超时），所以建议先打牢基础再来做这道题。
时梓繁在2018-07-17 14:58:13追加了内容
第2个是
初级光能
来个人
中级天翼
1
初级光能
需要用那个数论
修练者
数论题目，普通方法会超时
