我的笔记
#include <bits/stdc++.h>
using namespace std;
const int N=1e8+10;
bool s[N];
int prime[N/10],n,cnt=0;
void solve(int n){
s[0]=s[1]=0;
for(int i=2;i<=n;i++){
if(s[i]==0){
prime[++cnt]=i;
}
for(int j=1;j<=cnt&&i*prime[j]<=n;j++){
s[i*prime[j]]=1;
if(i%prime[j]==0){
break;
}
}
}
}
int main (){
cin >> n;
solve(n);
cout << cnt << endl;
/*for(int i=1;i<=n;i++){
cout << prime[i] << " ";
}
cout << endl << endl << endl;
for(int i=1;i<=n;i++){
cout << s[i] << " ";
}*/
return 0;
}
--------------------------------------------------------------------
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=5000000;
long prime[maxn]; // 存储一个个确定为质数的数
bool is_prime[maxn+1]; // 标记范围内所有数
int p = 0;
int sieve(int n){
p = 0;
for(int i=0;i<=n;i++)
is_prime[i]=true; // 所有数先标记为true
is_prime[0] = is_prime[1] = false; // 把数字0，1标记为质数
for(int i=2;i<=n;i++){
if(is_prime[i]) // 如果这个数没有被标记为false
{
prime[p++]=i; // 用prime数组存起来这个数，既存起了质数，又用p表示了质数个数
for(int j=i*i;j<=n;j+=i) // 这里没有优化时的写法是for(int j=2*i; j<=n; j++)。
//因为小于j(即i^2)内的合数都因为(根号j)(即i)内有更小的j的的因数而被排除
// 比如3^2 = 9，为什么不算2*3 = 6呢， 因为6<9,所以6因为3以内有更小的因数而直接被排除
is_prime[j]=false;
}
}
return p; // 返回质数个数
}
int main()
{
int n;
while(~scanf("%d",&n))
{
printf("质数个数是: %d\n",sieve(n));
printf("质数有:\n");
for (int i = 0; i<p; i++)
{
printf("%d ", prime[i]);
printf("\n\n");
}
}
return 0;
}
------------------------------------------------------------------------------------------------------------------
#include <iostream>
using namespace std;
int main(){
int n;
scanf("%d",&n);
printf("%d=",n);
for (int i = 2; i*i<= n; i++) {
while (n%i == 0){
printf("%d",i);
n /= i;
if (n != 1)
printf("*");
}
}
if(n>1){
cout << n ;
}
return 0;
}
----------------------------------------------------------------------------------------------------------------------
//约数个数
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 110, mod = 1e9 + 7;
int main()
{
int n;
cin >> n;
unordered_map<int, int> primes;//f.first 存放底数,f.second存放f.first的指数
while (n -- )
{
int x;
cin >> x;
for (int i = 2; i <= x / i; i ++ )
while (x % i == 0)
{
x /= i;
primes[i] ++ ;//用哈希表存因式分解中的指数
}
if (x > 1) primes[x] ++ ;//如果还没分解清,说明剩下的这个数是它的因数且只有一个
}
LL res = 1;
for (auto p : primes) res = res * (p.second + 1) % mod;//约数个数=(a1+1)(a2+1)...(ak+1)
cout << res << endl;
return 0;
}
------------------------------------------------------------------------------------------------------------------
//约数之和
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 110, mod = 1e9 + 7;
int main()
{
int n;
cin >> n;
unordered_map<int, int> primes;
while (n -- )
{
int x;
cin >> x;
for (int i = 2; i <= x / i; i ++ )
while (x % i == 0)
{
x /= i;
primes[i] ++ ;
}
if (x > 1) primes[x] ++ ; //注意是x>1
}
LL res = 1;
for (auto p : primes)
{
LL a = p.first, b = p.second;//p为底数,a为指数
LL t = 1;
while (b -- ) t = (t * a + 1) % mod;//求出 p0一直加到p的k的次方 的和//先求出公式中的每个括号内的值
res = res * t % mod;//把每个括号的值相乘
}
cout << res << endl;
return 0;
}
——————————————————————————————————————————————————————————
减法
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
int main(){
//计算 a - b = ans
int i,j,flag=0; //flag用来记录是否为负数, 1代表负数, 默认为0即正数
string a_s,b_s; //用字符串接受两个数字
int a[521]={0},b[521]={0},ans[521]={0}; //三个存数字数组, 记得初始化为0
cin>>a_s>>b_s; //接受输入的字符串型 a 和 b 存到 a_s 和 b_s 里
int len_a=a_s.length(),len_b=b_s.length(); //计算 a 和 b 的长度
int len=len_a>len_b?len_a:len_b; //计算 a 和 b 的最大长度, 确定做减法时的循环次数
for(i=0;i<len_a;i++) a[i]=a_s[len_a-1-i]-'0'; //将字符型数字转化为整形数字
for(i=0;i<len_b;i++) b[i]=b_s[len_b-1-i]-'0'; //注意要倒序存储, 后面输出的时候再倒一遍
if(len_a>len_b||len_a==len_b&&a_s>=b_s){ //当 a 大于等于 b 时
for(i=0;i<len;i++){
if(a[i]<b[i]){ //当对应位 a < b 时, 向高位借位
a[i+1]--; //高位减1
a[i]+=10; //这一位加10
}
ans[i]=a[i]-b[i]; //做减法
}
}
else{ //当 a 小于 b 时, a - b 为负数, 所以变为 b - a, 保证减法结果为正
flag=1; //负数标记
for(i=0;i<len;i++){
if(b[i]<a[i]){ //借位
b[i+1]--;
b[i]+=10;
}
ans[i]=b[i]-a[i];
}
}
if(flag) cout<<"-"; //输出负号
while(ans[len]==0&&len>0) len--; //去掉前置无用的 0
for(i=len;i>=0;i--){ //倒序输出结果
cout<<ans[i];
}
}
--------------------------------------------------------
加法
#include <iostream>
#include <cstring>
using namespace std;
int main(){
int num1[520]={0},num2[520]={0},ans[520]={0};//自己根据需要定义整形数组的大小
int temp,i,j; //temp是用来存进位的数字的
char num1c[520]={0},num2c[520]={0};//接受数字时用的字符数组
cin>>num1c>>num2c; //接收两个数字到字符数组（这是还是正向的）
int len1=strlen(num1c); //计算num1的长度
int len2=strlen(num2c); //计算num2的长度
//将两个字符型的数字 倒序存到对应整型数组里 （记得减字符‘0’）
//数字低位---------------->数字高位
for(i=len1-1;i>=0;i--){
num1[len1-1-i]=num1c[i]-'0';
}
for(i=len2-1;i>=0;i--){
num2[len2-1-i]=num2c[i]-'0';
}
//计算两个数字的和
//循环的时候可以全部过一遍，也可以根据两个数字的位数和进位来决定（循环次数会少一些）
//但我们要充分相信计算机的能力（bushi）
for(i=0;i<=520;i++){
ans[i]=num2[i]+num1[i]+temp;//求和
temp=ans[i]/10;//ans[i]如果大于10就进位
ans[i]%=10;//ans[i]取个位数
}
len2++;//最高位加 1 防止漏掉最后的进位
//当数字总位数大于1时，去掉开头的0
//不要全都去掉哦，不然0+0就没有输出了
while(ans[len2]==0&&len2>0) len2--;
//倒序打印出来就是答案了！！！！
for(i=len2;i>=0;i--){
cout<<ans[i];
}
}
------------------------------------------------------
#include <iostream>//chengfa
using namespace std;
int main(){
// 大整数 乘 大整数 是 大整数 乘 int 的进阶版
string a_s,b_s; //大整数 a 和 b 的字符串形式
int a[521]={0},b[521]={0},ans[521*2]={0}; //a, b, ans 的 int数组形式
int len_a,len_b,len,carry=0,i,j;
//len_a 为 a 的长度, len_b为 b 的长度, len 为 ans 的长度, carry为进位
//切记carry要初始化为 0！！！
cin>>a_s>>b_s; //接收两个整数 a, b
len_a=a_s.length();//分别计算长度
len_b=b_s.length();
for(i=0;i<len_a;i++) a[i]=a_s[len_a-1-i]-'0';//分别转为 int 型并倒序存储
for(i=0;i<len_b;i++) b[i]=b_s[len_b-1-i]-'0';
for(i=0;i<len_b;i++){ // 核心计算过程,外层循环为乘数, 内层循环为被乘数*int的高精乘低精算法
for(j=0;j<len_a||carry!=0;j++){
ans[i+j]+=a[j]*b[i]+carry; //注意ans的下标为 i+j ! a和 b下标对应它的循环变量
carry=ans[i+j]/10;
ans[i+j]%=10;
}
}
len=i+j; //数组最后一个数字为 ans[i+j], 所以 i+j 即为ans长度
while(ans[len]==0&&len>0) len--; // 去除前缀无用的 0
for(i=len;i>=0;i--){ //倒序输出
cout<<ans[i];
}
}
------------------------------------------------------
chufa
#include <iostream>
#include <string>
using namespace std;
bool judge(int* a,int* b,int len){ //判断len长度的 b 是否可以被 a 除
if(a[len]>0) return true; //如果 a 比 b 长, 一定可以除
for(int i=len-1;i>=0;i--){//从 a 的最高位开始比
if(a[i]>b[i]) return true;//除去相等位的最高位大于b,说明a比b大,可以除
else if(a[i]<b[i]) return false;//除去相等位的最高位小于b,说明a比b小，不可以除
}
return true;//a和b完全一样,可以除
}
int main(){
string a_s,b_s;
int a[521]={0},b[521]={0},ans[521]={0};
int i,j,len_a,len_b,len;
cin>>a_s>>b_s;
if(b_s=="0"){//除数不能为0
cout<<"除数不能为0"<<endl;
return 0;
}
len_a=a_s.length();//计算 a和 b的长度
len_b=b_s.length();
len=len_a-len_b; //结果最开始的下标
for(i=0;i<len_a;i++) a[i]=a_s[len_a-1-i]-'0';//字符型转int型
for(i=0;i<len_b;i++) b[i]=b_s[len_b-1-i]-'0';
for(i=len_a-len_b;i>=0;i--){
while(judge(a+i,b,len_b)){//当a可以被b减的时候一直进行，直到不能被减,即得到最终的商
ans[i]++; //记录a被b减的次数，即为除法的结果
for(j=0;j<=len_b-1;j++){//高精度减法的实现方法
if(a[i+j]<b[j]){
a[i+j+1]--;
a[i+j]+=10;
}
a[i+j]-=b[j];
}
}
}
while(a[len_a]==0&&len_a>0) len_a--;//去掉前缀无用的零
while(ans[len]==0&&len>0) len--;
for(i=len;i>=0;i--) cout<<ans[i];//输出结果
if(len<0) cout<<"0";//当被除数短于除数时,len<0不进行上一条语句,单独输出一个零
if(len_a>1||a[0]>0){//a最后没有减完的部分成为余数，余数为0就不输出
cout<<"余";
for(i=len_a;i>=0;i--) cout<<a[i];
}
}
加载中...