关于最大公约数的疑惑

清疚 2022-06-16 03:41 173阅读 0赞

## Description ##

小光是个十分喜欢素数的人，有一天他在学习最大公约数的时候突然想到了一个问题，他想知道从1到n这n个整数中有多少对最大公约数为素数的(x,y)，即有多少(x,y),gcd(x,y)=素数，1<=x,y<=n。但是小光刚刚接触最大公约数，不能解决这个问题，于是他希望你能帮助他解决这个问题。

## Input ##

一个整数N  (1<=N<=10^5)

## Output ##

(x,y)的个数

## Sample Input ##

5

## Sample Output ##

5

## HINT ##

(2,2) (2,4) (4,2) (3,3) (5,5)

Source

#include<iostream>
    using namespace std;
    int a[100010]={0};
    int ss(int x)
    {
    	int i,j;
    	if (a[x]){
    		return 1;
    	}
    	for (i=2; i<x; i++)
    	{
    		if (x%i==0)
    			break;
    	}
    	if (x==i)
    	{
    		a[x] = 1;
    		return 1;
    	}
    	return 0;
    }
    int gcd(int x,int y)
    {
    	int t;
    	if (x<y)
    	{
    		t=x; x=y; y=t;
    	}
    	while (y)
    	{
    		t = x%y;
    		x=y;
    		y=t;
    	}
    	return x;
    }
    int main()
    {
    	int n,i,j,cnt=0;
    	cin>>n;
    	for (i=2; i<=n; i++)
    	{
    		if (ss(i))
    		{
    			cnt++;
    		}
    		for (j=2; j<=n; j++)
    		{
    			if (i==j)
    			{
    				continue;
    			}
    			if (ss(gcd(i,j)))
    			{
    				cnt++;
    			}
    		}
    	}
    	cout<<cnt<<endl;
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，173人围观）

还没有评论，来说两句吧...

相关阅读

相关 JavaScript最大公约数

//最大公约数求解（辗转相除法） function gcd(a, b) { if (a % b === 0) { r...

怼烎@/ 2024年04月17日 05:28/ 0 赞/ 63 阅读

相关关于最大公约数gcd算法的扩展

1. 更多数字的最大公约数可以逐步分解为更小的最大公约数 `gcd(a, b, c) = gcd(gcd(a, b), c);` 2. 两个数的最小公倍数就是这

野性酷女/ 2023年01月10日 10:26/ 0 赞/ 171 阅读

相关求最大公约数

`迭代版本` function getCd(a, b) { if (a b < 0) return 1 if (a ==0 || b

深碍√TFBOYSˉ_/ 2023年01月04日 10:30/ 0 赞/ 179 阅读

相关最大公约数

什么是最大公约数 > 最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为（a，b），同样的，a，b，c的最大公约数记为（

小灰灰/ 2022年07月29日 06:26/ 0 赞/ 177 阅读

相关关于最大公约数的疑惑

Description 小光是个十分喜欢素数的人，有一天他在学习最大公约数的时候突然想到了一个问题，他想知道从1到n这n个整数中有多少对最大公约数为素数的(x,y)，即有

清疚/ 2022年06月16日 03:41/ 0 赞/ 174 阅读

相关最大公约数

public class GCD { //方法一 public static void gcd1(int a, int b) {

左手的ㄟ右手/ 2022年05月26日 01:28/ 0 赞/ 143 阅读

相关最大公约数

问题D：最大公约数时间限制：1秒内存限制：64 MB 提交：554解决：274 \[ [提交][Link 1] \] \[ [状态][Link 2] \] \[

末蓝、/ 2022年05月22日 12:20/ 0 赞/ 199 阅读

相关 __gcd最大公约数

\_\_gcd-最大公约数 1. 最大公约数（greatest common divisor，简写为gcd；或highest common factor，简写为hcf） 2

超、凢脫俗/ 2022年05月11日 13:44/ 0 赞/ 198 阅读

相关算法-最大公约数

最大公约数是一个很经典的数学问题，对于这个问题有四种通用的解法，质因数分解法，短除法，不过比较常用的还是辗转相除法，算法出自于欧几里的著作《几何原本》，还有一个就是出自《九章算

爱被打了一巴掌/ 2022年03月31日 17:12/ 0 赞/ 247 阅读

相关求最大公约数

求最大公约数 \\一.题目内容 \\运行最大公约数的常用算法，并进行程序的调式与测试，要求程序设计风格良好，并添加异常处理模块。 \\二.算法设计 \\四种函

以你之姓@/ 2022年03月10日 04:23/ 0 赞/ 284 阅读