【c++笔记】用c++解决一系列质数问题!

发布时间:2024年01月20日

? ? ? ? 质数是c语言和c++中比较常见的数学问题,本篇文章将带你走进有关质数的一系列基础问题,其中包含常见的思路总结,本篇文章过后,将会持续更新c++算法系列,感兴趣的话麻烦点个关注吧!

希望能给您带来帮助,谢谢您的观看!

目录

题目一:质数口袋

题目二:回文质数 Prime Palindromes

题目三:质数筛?编辑

?题目四:质因数分解

?做题总结:

①判断是否为质数的统一简单函数

②埃筛思想?

③一段时间以来对c语言与c++的感悟?


题目一:质数口袋

输入输出案例
输入100
输出
2
3
5
7
11
13
17
19
23
9

代码如下:

#include <bits/stdc++.h>
using namespace std;
int f(int n)
{
	int t=sqrt(n);
	for(int i=2;i<=t;i++)
	{
		if(n%i==0)
	{
		return 0;
	}
	}
	return n;
}

int main()
{
	int a,sum=0,coun=0;
	cin>>a;
	for(int i=2;i<=a;i++)
	{
	sum+=f(i);
	if(f(i))
	{
		printf("%d\n",i);
		coun++;
	} 
	if(sum>=a)
	break;	
	}
	printf("%d",coun);
	return 0;
}

题目二:回文质数 Prime Palindromes

输入输出案例
输入5 500
输出
5
7
11
101
131
151
181
191
313
353
373
383

?代码如下:

#include <bits/stdc++.h>
using namespace std;
int f(int n)
{
	int t=sqrt(n);
	for(int i=2;i<=t;i++)
	{
		if(n%i==0)
		return 0;
	}
	return n;
}

void ff(int n)
{
	int t,m=0;
	t=n;
	while(n!=0)
{
	m=m*10+n%10;
	n=n/10;
}
if(m==t)
printf("%d\n",t);
}

int main()
{
	int a,b,t;
	scanf("%d%d",&a,&b);
	for(int i=a;i<=b;i++)
	{
		if(f(i))
		{
			ff(i);
		}	
	}
	return 0;
}

题目三:质数筛

输入输出案例
输入
5
3 4 5 6 7
输出3 5 7

代码如下?

#include <bits/stdc++.h>
using namespace std;
void st(long a[],long n)
{
for(int i=0;i<n;i++)
{
	for(int j=2;j<=a[i];j++)
	{
		if(a[i]%j==0&&a[i]!=j)
		{
			a[i]=0;
			break;
		}
	}
	if(a[i]!=0&&a[i]!=1)
	printf("%ld ",a[i]);
}
}
int main()
{
	long n;
	scanf("%ld",&n);
	long a[n];
	for(int i=0;i<n;i++)
	scanf("%ld",&a[i]);
	st(a,n);
	return 0; 
}

?题目四:质因数分解

输入输出案例
输入21
输出7

代码如下?

void st(int n)
{
	int i,j;

	printf("%d",j); 
}
int main()
{
	int n;
	scanf("%d",&n);
	st(n);
	return 0;
}

?做题总结:

①判断是否为质数的统一简单函数

int f(int n)
{
	int t=sqrt(n);
	for(int i=2;i<=t;i++)
	{
		if(n%i==0)
		return 0;
	}
	return n;
}

很多情况下题目只要求质数部分,这个函数简单好用

②埃筛思想?

很多时候我们可以在数组中把质数定义为1,把非质数定义为0,这样就可以通过if条件语句对质数进行判断

同时这个方法对于把for循环条件里的i当作自然数的把握也十分有效

③一段时间以来对c语言与c++的感悟?

c语言与c++的写法实在是非常相同的,甚至很多时候只需要改一个头文件,但有的时候为了不tel,还是会选择性的去选择不同的函数,并且c++的函数较多,写代码时比较方便

?

文章来源:https://blog.csdn.net/2301_79982543/article/details/135720035
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。