首页 > 其他分享 >P5736 【深基7.例2】质数筛

P5736 【深基7.例2】质数筛

时间:2024-01-26 22:01:01浏览次数:33  
标签:P5736 int 质数 深基 样例 arr num

1.题目介绍

【深基7.例2】质数筛

题目描述

输入 \(n\) 个不大于 \(10^5\) 的正整数。要求全部储存在数组中,去除掉不是质数的数字,依次输出剩余的质数。

输入格式

第一行输入一个正整数 \(n\),表示整数个数。

第二行输入 \(n\) 个正整数 \(a_i\),以空格隔开。

输出格式

输出一行,依次输出 \(a_i\) 中剩余的质数,以空格隔开。

样例 #1

样例输入 #1

5
3 4 5 6 7

样例输出 #1

3 5 7

提示

数据保证,\(1\le n\le100\),\(1 \leq a_i \leq 10^5\)。

2.题解

2.1 子程序

思路

只要知道 如果一个数是质数,有 num = m * n;(m,n != 1,num), 如果有一个因子 m >= sqrt(num), 那么必然有另一个因子 n <= sqrt(num),所以我们只要找到这个n是否存在即可

代码

#include<bits/stdc++.h>
using namespace std; 
bool is_prime(int num){
	if(num == 1) return false;
	else if(num == 2) return true;
	for (int i = 2; i <= sqrt(num); i++){
		if (num % i == 0) return false;
	}
	return true;
}
int main(){
	int n;
	cin >> n;
	vector<int> arr(n);
	for (int i = 0; i < n; i++){
		cin >> arr[i];
		if(is_prime(arr[i])) cout << arr[i] << ' ';
	}
}

标签:P5736,int,质数,深基,样例,arr,num
From: https://www.cnblogs.com/trmbh12/p/17990825

相关文章

  • 洛谷题单指南-排序-P1271 【深基9.例1】选举学生会
    原题链接:https://www.luogu.com.cn/problem/P1271题意解读:最直接的计数排序问题,借助一个桶h[N],对被投票的候选人x执行h[x]++,再按顺序遍历输出即可。100分代码:#include<bits/stdc++.h>usingnamespacestd;constintN=1005;inth[N];intmain(){intn,m;......
  • P5734 【深基6.例6】文字处理软件
    1.题目介绍【深基6.例6】文字处理软件题目描述你需要开发一款文字处理软件。最开始时输入一个字符串作为初始文档。可以认为文档开头是第\(0\)个字符。需要支持以下操作:1str:后接插入,在文档后面插入字符串\(\texttt{str}\),并输出文档的字符串;2ab:截取文档部分,只保留文档......
  • P5733 【深基6.例1】自动修正
    1.题目介绍2.题解2.1字符串大小写转换思路str[i]-='a'-'A';注意这里转换方式,即减去偏移量(ASCII码表中,'a'在'A'前面,如果记不得偏移量,就直接写'a'-'A'即可)代码#include<bits/stdc++.h>usingnamespacestd;intmain(){ stringstr; cin>......
  • P5728 【深基5.例5】旗鼓相当的对手
    1.题目介绍2.题解2.1二维数组思路主要熟悉vector创建二维数组的方法vector<vector>ans(N,vector(3));这里第一个元素表明数组大小,第二个元素表明该二维数组的所有元素初始化为一个大小为3的一维数组vector(3)是一种匿名对象(anonymousobject)的写法。在这里,它是一个临时......
  • 质数判断&质因数分解
    引入众所周知,素数的判断在longlong级别是不能\(O(\sqrt{n})\)硬上的。那怎么办呢??参考文献。ababab,先来最低效的。以下复杂度均考虑高精。1.试除法\(O(\sqrtn)\)枚举,\(n\le10^{14}\)。优化只枚举质数,无法优化预处理质数时间。2.Millar-Rabinlonglong:\(O(k\t......
  • c# 求质数的方法
    质数定义法:质数是指只能被1和自身整除的正整数,即除了1和它本身以外没有其他因数。因此,判断一个数是否为质数,只需要将它分别除以2到它的平方根的整数,如果都不能整除,则它就是质数。这种方法比较简单直观,但对于较大的数会比较耗时。1staticboolIsPrime(intnum)2......
  • 客户案例 | 思腾合力助力某能源公司地质数据智能化计算平台建设
    石油行业是全球最大的行业之一,涉及到从地下或海底开采原油和天然气的勘探、开发、生产、运输、精炼和销售的全过程。石油不仅是世界上最主要的能源之一,还是化工产品的主要原料。石油行业的运作对全球经济有着重大影响,其价格波动可以影响到各国的经济状况和政策决策。客户需求与解决......
  • 【洛谷 P1923】【深基9.例4】求第 k 小的数(快速排序)
    【深基9.例4】求第k小的数题目描述输入(且为奇数)个数字(),输出这些数字的第小的数。最小的数是第小。请尽量不要使用nth_element来写本题,因为本题的重点在于练习分治算法。输入格式输出格式样例#1样例输入#15143215样例输出#12思路先快速排序,然后通过数组索引访......
  • 【洛谷 P1271】【深基9.例1】选举学生会 题解(计数排序)
    【深基9.例1】选举学生会题目描述学校正在选举学生会成员,有名候选人,每名候选人编号分别从1到,现在收集到了张选票,每张选票都写了一个候选人编号。现在想把这些堆积如山的选票按照投票数字从小到大排序。输入格式输入和以及个选票上的数字。输出格式求出排序后的选票编......
  • 打印100=200之间的素数(质数)
    只能被本身和1整除的数--素数#define_CRT_SECURE_NO_WARNINGS1#include<stdio.h>//1.试除法--低阶intmain(){ inti=0; intcount=0; for(i=100;i<=200;i++) { intj=0; for(j=2;j<=i;j++)//j从2开始是为了直接避免1这个数被除 { if(i%......