什么是函数？

一个 C++ 程序无论大小，都由一个或者多个函数组成，而且其中必须有且只有一个函数 main() ，称之为主函数 ，由函数 main() 调用其他函数来完成程序的特定功能。当然，其他函数之间也可以按照规则互相调用。
C++ 中的函数由一段相对独立的代码组成，这段代码能实现某一项具体、独立、完整的功能。函数在程序设计中的作用主要有两个，一是代码重用，二是问题分解。
代码重用是保证同一个函数可以被一个或多个函数调用任意多次，从而减少重复代码的编写。问题分解可以保证一个大的程序（或者说软件），按照模块化编程思想，由大化小，分解成若干个结构清晰、功能独立、调试方便的函数，甚至给若干人合作完成，从而提高开发效率。

函数的定义和调用

typeName functionName(parameterList){
    return value;
}

functionName(parameterList)

函数求质数问题

质数与合数

定理：一个大于1的正整数，只能被1和自身整除，不能被其他正整数整除， 这样的正整数叫做质数。

一个正整数，除了能被1和自身整除外，还可以被其他的正整数整除，这样的正整数叫做合数。

如果一个正整数a有一个因数b，而b又是质数，则b就叫做a的质因数。

全体正整数可以分为3类：

1.整数

2.全体质数

3.全体合数

引理：如果a是一个大于1的整数，则a的大于1的最小因数一定是质数。

证：

1.如果a是一个质数，a的大于1的因数只有一个，就是a，结论成立。

2.如果a是一个合数，除1和a之外a还有其他正因数，假设b是这些正因数中最小的，假定b是合数，一定有1<c<b，c|b，b|a，即c|a，与假设矛盾。 此引理说明了：任何大于1的整数都至少有一个质因数。

质数个数定理：定义 π(x)为不大于x的质数的个数：

bool is_prime(int n){
    for(int i = 2; i <= n / i; i++)
        if(n % i == 0)
            return false;
    
    return true;
}

筛法求质数

朴素筛法： 枚举2到n的每个数i，将2i，3i，··· 均标记为合数； 枚举完后仍没有被标记的数即为质数。

时间复杂度：

简要证明调和级数前n项和≈logn：

vector<int> get_primes(int n){
  
  	vector<int> v;
  
	for(int i = 2; i <= n; i++){
    	if(!book[i])
          	v.push_back(i);
      	for(int j = 2 * i; j <= n; j += i) book[j] = true;
    }
  
  	return v;
}

埃氏筛法（Eratosthenes）： 只有质数才可能标记后面的合数：时间复杂度：O(nloglogn)。

vector<int> get_primes(int n){
  
  	vector<int> v;
  
	for(int i = 2; i <= n; i++){
    	if(!book[i]){
          	v.push_back(i);
        	for(int j = 2 * i; j <= n; j += i) book[j] = true;
        } 	
    }
  
  	return v;
}

指针变量

• 指针也是一种数据类型，指针变量也是一种变量
• 指针变量指向谁，就把谁的地址赋值给指针变量
• *操作符操作的是指针变量指向的内存空间
• 使用sizeof()测量指针的大小，取决于操作系统

char ch = 'A';
int a = 1;

printf("%p %p\n", &ch, &a);

int a = 1;
int* b = &a;
*b = 2;
cout << a << " " << *b << endl;

野指针和空指针

野指针：C++中创建指针时，计算机将分配用来存储地址的内存，但是不会分配用来存储指针所指向数据的内存。比如：p指针指向的空间是不确定的，通过间接操作修改了p指向空间的数据，很可能是操作系统中重要的数据，就发生不可预知的危险，因此，声明指针时一定要初始化。

int *p;
*p = 100;
cout << *p << endl;

空指针：野指针和有效指针变量保存的都是数值，为了标志此指针变量没有指向任何变量(空闲可用)，C语言中，可以把NULL赋值给此指针，这样就标志此指针为空指针，没有任何指针。

• int *p = NULL
• NULL是一个值为0的宏常量：#define NULL((void *)0)

万能指针void *

有时候，一个指针根据不同的情况，指向的内容是不同类型的值，我们可以先不明确定义它的类型，只是定义一个无类型的指针，以后根据需要再用强制类型转换的方法明确它的类型。

#include <iostream>
using namespace std;

int a = 10;
double b = 3.5;
void* p; 
int main(){
	p = &a;
	cout << *(int*)p << endl;
	p = &b;
	cout << *(double*)p << endl;
	cout << *(long long*)p << endl;
	return 0;
}

输出：
10
3.5
4615063718147915776

const修饰的指针变量

int a = 100, b = 200;

// 指向常量的指针
// 修饰*，指针指向可以改变，指针指向内存区域不能修改
const int * p1 = &a;
// *p1 = 111;
p1 = &b;
cout << *p1 << endl;

// 指针常量
// 修饰p2，指针指向内存区域可以改变，指针指向不可以改变
int * const p2 = &a;
// p2 = &b;
*p2 = 222;
cout << *p2 << endl;	

指针数组

数组的每个元素都是指针类型。

#include <iostream>
#include <cstdio>
using namespace std;

int main() {

    int a = 1, b = 2, c = 3;
    int* p[] = {&a, &b, &c};

    for(int i = 0; i < sizeof(p) / sizeof(p[0]); i++)
        cout << *p[i] << " ";
	
	return 0;
}

多重指针

指向指针的指针。

#include <cstdio>

int a = 10;
int* p;
int** pp;	// 定义双重指针 
int*** ppp; // 定义三重指针
 
int main() {
	p = &a;		// 将p指向a
	pp = &p;	// 将pp指向p
	ppp = &pp;  // 将ppp指向pp
	printf("a=%d=%d=%d\n", *p, **pp, ***ppp); 
	return 0;
}

引用

引用是给变量起别名，比指针更加简洁。

#include <iostream>
#include <cstdio>
using namespace std;

int main() {
    
    // 引用的本质是常指针，因此必须初始化
    int a = 10;
    int& b = a; // int* const b = &a;

    b = 20; // *b = 20;

    cout << a << " " << b << endl;
	
	return 0;
}

函数引用传参。

#include <iostream>
#include <cstdio>
using namespace std;

int f(int& x){
    x *= 2;
    return x * 3;
}

int main() {

    int a = 10;
    cout << f(a) << " " << a << endl;
	
	return 0;
}

数组引用：

int a[5] = { 1, 2, 3, 4, 5 };
int(&aref)[5] = a;

aref[0] = 6;

for (int i = 0; i < 5; i++) cout << a[i] << " "; // 6 2 3 4 5

函数参数实现变量交换

函数内部定义的变量叫做局部变量，生命周期仅限于函数内部。

函数外部定义的变量叫做全局变量，生命周期等同于程序的周期。

#include <iostream>
#include <cstdio>
using namespace std;

void swap1(int a, int b){
    int t = a;
    a = b;
    b = t;
    cout << "函数内部: " << a << " " << b << endl;
}

void swap2(int* a, int* b){
    int t = *a;
    *a = *b;
    *b = t;
}

void swap3(int& a, int& b){
    int t = a;
    a = b;
    b = t;
}

int main() {

    int a = 1, b = 2;

    // swap1(a, b);
    // swap2(&a, &b);
    swap3(a, b);

    cout << "函数外部：" << a << " " << b << endl;
	
	return 0;
}

数组做函数参数

#include <iostream>
#include <cstdio>
using namespace std;

int n;
int a[110];

void f(const int a[]){
    // a[1] *= 2;
    for(int i = 1; i <= n; i++)
        cout << a[i] << " ";
}

void f2(const int* a){
    // a[1] *= 2;
    for(int i = 1; i <= n; i++)
        cout << a[i] << " ";
}

int main() {

    cin >> n;

    for(int i = 1; i <= n; i++)
        cin >> a[i];

    f(a);

    cout << endl << "---------------" << endl;

    for(int i = 1; i <= n; i++)
        cout << a[i] << " ";
	
	return 0;
}

疯狂刷题

• P268 曼哈顿距离
• P269 三角形面积
• P270 统计闰年
• P275 打印字符三角形
• P271 数的分离
• P153 素数大酬宾
• P274 哥德巴赫猜想
• P276 孪生素数