关于linux:OS大作业二多线程程序测试一个数是否为完全数

题目：

如果一个数N的所有因数（不包含N自身）的和还是N，则N是一个齐全数。如果一个数N的所有因数（不包含N自身）的和还是N，则N是一个齐全数，如6和28，输出是一个整数N，如果N是齐全数则输入true，否则输入false。主程序从命令行读取数字N和P，创立P个线程，将1~N这N个数分给各个线程，保障两个线程不会分到雷同的数。每个线程判断这些树是不是N的因数，如果是，那么放到一个共享的缓冲区中。在父过程中用适合的同步办法期待所有的线程执行结束后，判断N是否是齐全数，即判断是否N的所有因数之和还是N（提醒：你能够将测试的数限定在1至N的平方根来减速计算过程。）

思路

• 首先，题目只要求判断一个数是否为齐全数，并且要求通过多线程实现，那么每次线程进行的都只是齐全数的子问题：找出N的因数。即判断 N%cnt==0 是否为零。若为零，阐明cnt是N的因数，将其统计到和sum当中。
• 错误想法：只是单纯的创立N个线程让每一个线程顺次判断1…N-1是否为N的因数。
• 纠正：线程能够有很多个，应该让多个线程去抢夺 子问题 的执行，但又必须保障各线程不能同时执行子问题而造成同一个因数被屡次计算。因而，必须对子问题进行加锁解决。

void* isFactor(void* args){
    while(/* 线程期待条件 */){
        
        pthread_mutex_lock(&mutex);
        
        //判断是否为因数
        
        pthread_mutex_unlock(&mutex);
    }
    return NULL;
}

• 保障1…N-1不会被反复判断：各个线程会抢夺mutex_lock，但同一时刻只能有一个线程在执行子问题。因而咱们设定一个值cnt，来代表1…N-1这些数。并且cnt的变动只能在锁内进行，这就保障了1…N-1中的每个数只会被执行一次。

• 线程期待与完结条件： sum ！= N 之前，所有线程都未完结，并且只有一个线程在拜访锁，此线程拜访完结后开释锁资源，再与其余线程一起抢夺锁资源。每次抢夺锁资源的线程数是始终不变的，始终都是创立的线程数。 sum == N 之后，所有线程同时完结。因而，线程期待条件为 sum != N 。

  int cnt = 1,sum = 0;
  void* isFactor(void* args){
    while(sum != N){
        
        pthread_mutex_lock(&mutex);
        
        if(N % cnt == 0){
            sum += cnt;
        }
        cnt++;
        
        pthread_mutex_unlock(&mutex);
    }
    return NULL;
  }
  

优化

依据题目提醒，若n是N的因数，则N/n也肯定为N的因数。因而，实际上最多只需

$$
\sqrt{N}
$$

次判断即可。因而程序可批改为：

int cnt = 2,sum = 1;
void* isFactor(void* args){
    while(cnt < sqrt(N)){
        
        pthread_mutex_lock(&mutex);
        
        if(N % cnt == 0){
            sum = sum + cnt + N/cnt;
        }
        cnt++;
        
        pthread_mutex_unlock(&mutex);
    }
    return NULL;
}

残缺代码如下：

#include <stdio.h>
#include <pthread.h>
#include <math.h>

#define MAX_N_thread 1000
#define TRUE 1
#define FALSE 0


int N;
int cnt = 2,sum = 1;
pthread_mutex_t mutex=PTHREAD_MUTEX_INITIALIZER;

void* isFactor(void* args){
    while(cnt < sqrt(N)){
        
        pthread_mutex_lock(&mutex);
        
        if(N % cnt == 0){
            sum = sum + cnt + N/cnt;
        }
        cnt++;
        
        pthread_mutex_unlock(&mutex);
    }
    return NULL;
}

int main() {
    pthread_t th[MAX_N_thread];
    
    
    int P,NArray[MAX_N_thread];
    printf("Input N and P:");
    scanf("%d%d",&N,&P);
    
    //creat P threads
    for(int i = 1;i <= P;i++){
        pthread_create(&th[i], NULL, isFactor, NULL);
    }
    

    for(int i = 1;i <= P;i++){
        pthread_join(th[i], NULL);
    }
    
    
    printf("sum = %d",sum);
    return 0;
}