OpenMP并行计算程序设计-n以内的完数的个数

柔光的暖阳◎ 2022-07-16 11:50 201阅读 0赞

# 1.问题描述 #

一个数如果恰好等于它的因子之和，这个数就称为“完数”。例如6=1＋2＋3，再如8的因子和是7（即1+2+4），8不是完数。输入一个数n，编程找出n以内的所有完数及其个数。

# 2.算法设计 #

## 2.1 串行算法设计 ##

串行算法步骤如下

①因为1不算入一个完数，所以令数i=2，初始化答案值ans=0；

②因为1是任何数的一个因数，所以可初始化因数之和sum=1；

③令数k=2；

④如果数i能整除数k，说明k是i的一个因数，则sum += k；

⑤若k<=i/2（控制范围保证i%k能进行计算），++k，转到④，否则转到⑥；

⑥若sum = i，++ans；

⑦若i <=n，++i，转到②，否则转到⑧；

⑧函数返回答案值ans。

## 2.2 并行算法设计 ##

并行算法步骤如下

①因为1不算入一个完数，所以令数i=2，初始化答案值ans=0；

②“\#pragmaomp parallel for”

②因为1是任何数的一个因数，所以可初始化因数之和sum=1；

“\#pragmaomp parallel for”

③令数k=2；

“\#pragmaomp critical”

④如果数i能整除数k，说明k是i的一个因数，则sum += k；

⑤若k<=i/2（控制范围保证i%k能进行计算），++k，转到④，否则转到⑥；

⑥若sum = i，++ans；

⑦若i <=n，++i，转到②，否则转到⑧；

⑧函数返回答案值ans。

## 2.3 理论加速比分析 ##

若p个处理器上数据量为n，则S=np/（n+2plogp）。

本机测试中，p=4：若n=10000，则S=3.9981；若n=100000，则S=3.9998。

/*问题描述：一个数如果恰好等于它的因子之和，这个数就称为“完数”。例如6=1＋2＋3，再如8的因子和是7（即1+2+4），8不是完数。编程找出n以内的所有完数。
    */
    // test.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include <cstdlib>
    #include <iostream>
    #include <cmath>
    #include <ctime>
    #include <omp.h>
    #include <windows.h>
    using namespace std;
    
    int OMP_Perfect(long long n)       //并行计算n以内的完数个数
    {
    	int ans = 0;                  // n以内的完数个数
    	long long i, k;                      //循环变量
    #pragma omp parallel for
    	for (i = 2; i <= n; i++)  //1不算入一个完数。
    	{
    		long long sum = 1;                 //数的因数之和,1是任何数的一个因数。
    #pragma omp parallel for reduction(+:sum)              //解决sum数据冲突
    		for (k = 2; k <= i / 2; k++)  //k<=i/2是要保证i%k能进行计算。
    			if (i%k == 0)
    				sum += k;       //因数之和
    		if (sum == i)       //找到一个完数
    			++ans;                 //函数返回答案值ans
    	}
    	return ans;
    }
    int Perfect(long long n)
    {
    	int ans = 0;                  // n以内的完数个数
    	long long i, k;                      //循环变量
    	for (i = 2; i <= n; i++)  //1不算入一个完数。
    	{
    		long long sum = 1;                 //数的因数之和,1是任何数的一个因数。
    		for (k = 2; k <= i / 2; k++)  //k<=i/2是要保证i%k能进行计算。
    			if (i%k == 0)
    				sum += k;       //因数之和
    		if (sum == i)       //找到一个完数
    			++ans;                 //函数返回答案值ans
    	}
    	return ans;
    }
    int main()
    {
    	long long n;
    	cin >> n;
    	printf("%lld以内的完数有:\n", n);
    	clock_t t1, t2;
    	t1 = clock();
    	printf("Sum= %d\n", OMP_Perfect(n)); //输出并行计算出的n以内的完数个数
    	t2 = clock();
    	printf("parallel time: %d\n", t2 - t1);//输出并行计算时间
    	t1 = clock();
    	printf("Sum= %d\n", Perfect(n)); //输出串行计算出的n以内的完数个数
    	t2 = clock();
    	printf("serail time: %d\n", t2 - t1); //输出串行计算时间
    	system("pause");
    	return 0;
    }

![20161017211922946][]

![20161017211935931][]

[20161017211922946]: /images/20220716/781a9433e0b6418f9e72f4a59fad11c3.png
[20161017211935931]: /images/20220716/64675041e4ae44fe9f3c594940e40a46.png