【洛谷 P1075】[NOIP2012 普及组] 质因数分解 题解(判断质数)

简介: NOIP2012普及组题目,给定合数$n$由两个不同质数乘积组成,求较大质数。输入一个正整数$n$,输出较大质因子。例如输入21,输出7。代码使用C++,通过循环和质数判断找到能整除$n$的质数,再求另一个质数,并输出较大者。

[NOIP2012 普及组] 质因数分解

题目描述

已知正整数 $n$ 是两个不同的质数的乘积,试求出两者中较大的那个质数。

输入格式

输入一个正整数 $n$。

输出格式

输出一个正整数 $p$,即较大的那个质数。

样例 #1

样例输入 #1

21

样例输出 #1

7

提示

$1 \le n\le 2\times 10^9$

NOIP 2012 普及组 第一题

思路

求能整除n的质数,再用n除以该质数得到另一个质数,输出这两个质数中较大的一个。

AC代码

#include <iostream>
#include <algorithm>
#define AUTHOR "HEX9CF"
using namespace std;

int main() {
   
    int n;
    cin >> n;
    for(int i = 2; i < n; i++){
   
        int p = 1;
        for(int j = 2; j < i; j++){
   
            if(!(i % j)){
   
                p = 0;
                break;
            }
        }
        if(p && !(n % i)){
   
            int b = n / i;
            cout << max(i, b) << endl;
            break;
        }
    }
    return 0;
}
目录
相关文章
|
5月前
【洛谷 P1307】[NOIP2011 普及组] 数字反转 题解(取余)
NOIP2011普及组试题,要求反转整数N的位得到新数,保持正负号和非零最高位。输入一个整数N,输出反转后的新数。样例输入1:123,输出:321;样例输入2:-380,输出:-83。代码使用取余法实现,处理负数时保留符号。
39 0
|
5月前
【洛谷 P1980】[NOIP2013 普及组] 计数问题 题解(取余)
NOIP2013普及组计数问题,求区间[1, n]内数字x出现的次数。输入为n和x,输出x的出现次数。样例输入11 1,输出4。代码通过逐位检查每个数是否等于x来计数,适用于$n\leq10^6$,$0\leq x\leq 9$的情况。
51 0
|
5月前
|
C++
【洛谷 P1307】[NOIP2011 普及组] 数字反转 题解(字符串)
**NOIP2011普及组题目:给定整数N,反转其位得到新数。新数首位非0(除非N=0)。输入0时直接输出0,其他情况输出反转后的数,考虑负数及前导0。提供的C++代码实现通过读入字符串,反转数字顺序并处理符号和前导0。**
29 0
|
5月前
|
C++
【洛谷 P1044】[NOIP2003 普及组] 栈 题解(递归+记忆化搜索)
**NOIP2003普及组栈问题**:给定操作数序列1到n,仅允许push(进栈)和pop(出栈)操作。目标是计算所有可能的输出序列总数。输入包含一个整数n(1≤n≤18)。示例输入3,输出5。当队列空时返回1,栈空则只能入栈,栈非空时可入栈或出栈。AC C++代码利用记忆化搜索求解。
71 1
|
5月前
|
机器学习/深度学习 人工智能
【洛谷 P1028】[NOIP2001 普及组] 数的计算 题解(递推)
在NOIP2001普及组的数的计算题目中,给定自然数`n`,需构造遵循特定规则的合法数列。合法序列始于`n`,新元素不超过前一项的一半。任务是找出所有这样的数列数量。例如,当`n=6`时,合法序列包括`6`, `6,1`, `6,2`, `6,3`, `6,2,1`, `6,3,1`。程序通过动态规划求解,当`i`为奇数时,`a[i] = a[i - 1]`;为偶数时,`a[i] = a[i - 1] + a[i / 2]`。代码中预处理数组`a`并输出`a[n]`作为答案。输入`n`后,程序直接计算并打印合法数列个数。
48 0
|
5月前
|
机器学习/深度学习 存储
【洛谷 P1028】[NOIP2001 普及组] 数的计算 题解(递归)
**NOIP2001普及组数的计算**:给定自然数\( n \),构造数列,新数不超过序列最后一项一半。求合法数列个数。输入\( n \)(\(1 \leq n \leq 10^3\))。样例:输入6,输出6。递归解决,代码中定义函数`f`实现递归计算,总和存储在`cnt`中,最后输出。
48 0
|
5月前
【洛谷 P1035】[NOIP2002 普及组] 级数求和 题解(循环)
**NOIP2002普及组题目:求级数$S_n=1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}$超过$k$的最小$n$。给定$1\leq k\leq 15$,输出满足$S_n&gt;k$的$n$。输入$1$个整数$k$,输出相应$n$。例如,输入$1$,输出$2$。代码中使用double确保精度,通过累加求和判断条件找到$n$。**
36 0
|
5月前
【洛谷 P2669】[NOIP2015 普及组] 金币 题解(循环)
`NOIP2015`普及组题目,骑士按周期领金币:第一天1枚,随后$n$天每天$n$枚,然后$n+1$天每天$n+1$枚。给定天数$k$,求总金币数。输入$k$,输出金币总数。样例输入6,输出14;输入1000,输出29820。代码使用循环和变量控制周期,累计金币数。
90 0
|
5月前
【洛谷 P1088】[NOIP2004 普及组] 火星人 题解(全排列+向量)
**火星人问题摘要:** NOIP2004普及组竞赛中的题目,涉及火星人用手指的排列表示数字。人类需计算火星人数字与给定数值之和的新排列。给定火星人手指数N(≤10000),加上的数M(≤100),以及初始排列,要求输出新排列。30%的数据中N≤15,60%的数据中N≤50。使用`next_permutation`函数找到第M个排列。样例:N=5, M=3, 初始排列1 2 3 4 5,输出1 2 4 5 3。
39 0
|
5月前
【洛谷 P1036】[NOIP2002 普及组] 选数 题解(深度优先搜索+判断质数+枚举子集)
**NOIP2002普及组选数问题**:给定$n$个整数和一个整数$k$,需找出所有$k$个数的组合,计算它们的和为素数的种类数。输入包含$n$和$k$,以及$n$个整数;输出是符合条件的组合数。例如,对于输入`4 3`和数组`[3, 7, 12, 19]`,输出为`1`。代码使用递归枚举子集并检查质数的方法。
51 0