Search code examples
c++vectorparallel-processingopenmppragma

trying to parallelize my code however when I run it, it never gives the correct output


I have a program that initializes a vector of 1,000,000 size and then finds all the prime numbers in it. The primes are stored in a new vector, I then iterate through that vector and try to find all of the happy numbers in it. I am trying to use task parallelism to split the work between 2 threads however I never return any output at all. here is the definition of a happy number A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number either equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers, while those that do not end in 1 are unhappy numbers (or sad numbers).

#include <omp.h>
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include<bits/stdc++.h>
#include<vector>
#include<numeric>

using namespace std;

void funcA();
void funcB();

int squaresum(int n){
    int sum=0;
    while(n){
        int d=n%10;
        sum+=d*d;
        n=n/10;
}
   return sum;
}

bool ishappy(int n){
set<int> s;
s.insert(n);

while(1){
    if(n==1) return true;
    n=squaresum(n);

    if(s.find(n)!=s.end()) return false;
    s.insert(n);
}
return false;
}
bool isprime(int n)
{

if (n <= 1)
    return false;
if (n <= 3)
    return true;


if (n % 2 == 0 || n % 3 == 0)
    return false;

for (int i = 5; i * i <= n; i = i + 6)
    if (n % i == 0 || n % (i + 2) == 0)
        return false;

return true;
}


int getHappyCount(int start, int size, int& happy)
{
int holder = size;
vector<int> num(size);
for(int i=start;i<start+size;i++) num[i]=i+1;

vector<int> prime;

for(int i=0;i<holder;i++)
{
    if(isprime(num[i])) prime.push_back(num[i]);
}

int count=0;
 for(int i=0;i<prime.size();i++)
{
     if(ishappy(prime[i])) count++;
}

#pragma omp atomic
happy += count;
}

int main()
{
int happy = 0;

#pragma omp parallel num_threads(2)
{
   #pragma omp sections
   {
      #pragma omp section

      {
        (void) getHappyCount(0, 500000, happy);
        printf("there are %d happy prime numbers \n", happy);
      }

      #pragma omp section

      {
        (void) getHappyCount(500000,  500000, happy);
        printf("there are %d happy prime numbers \n", happy);
      }
   }

}

    printf("there are %d happy prime numbers \n", happy);
    return 0;
 }

Solution

  • vector<int> num(size);
    for (int i = start; i < start + size; i++)
      num[i] = i + 1;
    

    This is obviously wrong unless start is zero. In all other cases, num[i] causes out-of-bound access of the num vector. You can switch to, for example:

    for (int i = 0; i < size; i++)
      num[i] = start + i + 1;
    

    Also, missing return statement in getHappyCount body implies undefined behavior. You should learn to understand warnings before you explicitly suppress them. Simply change the return type to void, or return something.