The objective of this homework is to get familiar with the editing and compilati

Question

The objective of this homework is to get familiar with the editing and compilation environment on Linux Raspberry Pi cluster and to write a C++ program.

Create a relPrimes.cpp file to do the following task.

Create a program which prints out all relatively prime numbers between two numbers, and gives how many pairs there are.

Two numbers are relatively prime if they share no common divisors other than 1 and themselves. For example 4 and 5 are relatively prime, yet 4 and 6 are not because 2 divides each of them. The C++ modulo operator (%) is useful for finding if two numbers are relatively prime. The brute force method is perfectly fine to use here, or you can use a more advanced algorithm. Hint: For all integers less than the given ones, see if they evenly divide both.

Your program should accept two number on the command-line (think argc argv), make sure the first is less than the second, and find all pairs of numbers between them (inclusive) that are relatively prime. If two numbers are not provided or are in the wrong order, give an error message and exit.

It should also print how many pairs it found. Be sure not to repeat pairs! See below for example output.

$ ./a.out 0 5
(1,2)
(1,3)
(1,4)
(1,5)
(2,3)
(2,5)
(3,4)
(3,5)
(4,5)
There are 9 relatively primes between 1 and 5
$ ./a.out 100 120

(100,101)

(100,103)

...

(118,119)

(119,120)

There are 129 relatively primes between 100 and 120

Speed is not important here, just make sure it finds the correct number of pairs.

Explanation / Answer

#include<iostream>
#include <sstream>

using namespace std;

int main(int argc, char** argv)
{
    int a[2];
    int found;
    int count;
    for (int i = 1; i < argc; ++i){
        stringstream str(argv[i]);
        str >> a[i-1];
    }
    if (a[0] > a[1]){
        cout << "Invalid input:First number should be less than the second nunber"<< endl;
        return 0;
    }
    count = 0;
   
    for (int i = a[0]; i<=a[1]; i++){
        if (i == 0)
           continue;
        for (int j = i+1; j<=a[1]; j++){
            found = 0;
            for (int k = 2; k<j; k++){
                if (i % k == 0 && j % k == 0){
                  found = 1;
                  break;
                }
            }
            if (found == 0){
               cout << i << " " << j << endl;
               count ++;
            }
        }
    }
    cout << "There are " << count << " relatively primes between " << a[0] << " and " << a[1] << endl;
    
    return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.