筛法
题目描述
用筛法求N以内的素数。
输入
N
输出
0~N的素数
样例输入
100
样例输出
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
#include<bits/stdc++.h>
using namespace std;
bool f[1000005];
int main()
{
int n;
cin>>n;
f[1]=0;
for(int i=2;i<=n;i++)
f[i]=1;
for(int i=2;i<=n;i++)
{
if(f[i]==1)
{
for(int j=2;j*i<=n;j++)
f[i*j]=0;
}
}
for(int i=2;i<=n;i++)
if(f[i])
cout<<i<<endl;
}
快速幂
题目描述
给定A,B,P,求(A^B) mod P。
输入
输入共一行。
一行有三个数,N,M,P。
输出
输出共一行,表示所求。
共10组数据
对100%的数据,A,B为long long范围内的非负整数,P为int内的非负整数。
样例输入
2 5 3
样例输出
2
#include <stdio.h>
int main()
{
long long n, m, p;
int sum = 1;
scanf("%lld %lld %lld", &n, &m, &p);
n %= p;
while (m>0)
{
if (m % 2 == 1)
{
sum = (sum * n) % p;
}
m /= 2;
n = (n * n) % p;
}
printf("%d\n", sum);
return 0;
}
快速排序
题目描述
用递归来实现快速排序(quick sort)算法。快速排序算法的基本思路是:假设要对一个数组a进行排序,且a[0] = x。首先对数组中的元素进行调整,使x放在正确的位置上。同时,所有比x小的数都位于它的左边,所有比x大的数都位于它的右边。然后对于左、右两段区域,递归地调用快速排序算法来进行排序。
输入
输入只有一行,包括若干个整数(不超过10个),以0结尾。
输出
输出只有一行,即排序以后的结果(不包括末尾的0。
样例输入
5 2 6 1 7 3 4 0
样例输出
1 2 3 4 5 6 7
#include<stdio.h>
#include<string.h>
int a[10];
void quicksort(int left,int right)
{
int i=left,j=right,t,temp;
temp=a[left];
if(left>right)
return;
while(i!=j)
{
while(a[j]>=temp&&i<j)
j--;
while(a[i]<=temp&&i<j)
i++;
if(i<j)
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
a[left]=a[i];
a[i]=temp;
quicksort(left,i-1);
quicksort(i+1,right);
}
int main()
{
int i=0;
while(i<10)
{
scanf("%d",&a[i]);
if(a[i]==0)
break;
else
{
i++;
}
}
quicksort(0,i-1);
for(int j=0;j<i;j++)
printf("%d ",a[j]);
return 0;
}