C++ problem

[forta2k]

Hello,
I have to write a program which displays all the numbers with 3 digits which have only 4 prime divisors. E.g.: 210, 330, 390, 420 etc.
I've tried this, but the program doesn't display anything.

  #include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int n, div=1, OK=1, nr=0, d=3;
    for(int n=100;n<=999;n++)
    {
     while(div<n)
    {
        if(n<3 or n%2==0) {OK= (n==2);}
        while(d<=sqrt(n) and OK==1)
        {
            if(n%d==0) {OK=0;}
            else {d+=2;}
        }
        if(n%div==0 && OK==1) {nr++;}
        OK=1;
        div++;
        if(nr==4)
        {
            cout<<n;
        }
        nr=0;
    }
    }
    return 0;
}

[lastchance]

I assume that you mean 4 DISTINCT prime factors; e.g. from your example
420 = 2 x 2 x 3 x 5 x 7 (5 factors; only 4 distinct)

The following has a lot of redundancy for your task - it continues factorising a number long after it has surpassed 4 distinct factors. However, I quite like the individual routines, so I leave it to you to optimise it for your problem.

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

//============================

int smallestFactor( int n )            // returns smallest factor of n (which must be prime unless n=1)
{
   int test = 2;
   int maxTest = sqrt( n );

   while ( test <= maxTest ) 
   {
      if ( n % test == 0 ) return test;
      test++;
   }
   return n;                           // default (including n=1)
}

//============================

vector<int> factorise( int n )         // factorises n ( > 1 ) into prime factors (smallest first); returns as a vector
{
   vector<int> factorList;
   int p;

   while ( n != 1 )
   {
      p = smallestFactor( n );   n /= p;
      factorList.push_back( p );
   }
   return factorList;
}

//============================

template <class T> int countDistinct( vector<T> V )        // counts distinct elements of a sorted vector
{
   if ( V.size() == 0 ) return 0;

   T current = V[0];
   int count = 1;
   for ( int i = 1; i < V.size(); i++ )
   {
      if ( V[i] != current )
      {
         current = V[i];
         count++;
      }
   }
   return count;
}

//============================

void writeFactors( int n, vector<int> factors )            // writes out (pre-)computed factors for a number
{
   cout << "Number: " << n;
   cout << "    Factors: " << factors[0];
   for ( int i = 1; i < factors.size(); i++ ) cout << " x " << factors[i];
   cout << endl;
}

//============================

int main()
{
   int n1 = 100, n2 = 999;                        // range to be searched
   int targetDistinct = 4;                        // number of distinct factors

   for ( int n = n1; n <= n2; n++ )
   {
      vector<int> factors = factorise( n );
      int distinct = countDistinct( factors );
      if ( distinct == targetDistinct ) writeFactors( n, factors );
   }
}

Number: 210    Factors: 2 x 3 x 5 x 7
Number: 330    Factors: 2 x 3 x 5 x 11
Number: 390    Factors: 2 x 3 x 5 x 13
Number: 420    Factors: 2 x 2 x 3 x 5 x 7
Number: 462    Factors: 2 x 3 x 7 x 11
Number: 510    Factors: 2 x 3 x 5 x 17
Number: 546    Factors: 2 x 3 x 7 x 13
Number: 570    Factors: 2 x 3 x 5 x 19
Number: 630    Factors: 2 x 3 x 3 x 5 x 7
Number: 660    Factors: 2 x 2 x 3 x 5 x 11
Number: 690    Factors: 2 x 3 x 5 x 23
Number: 714    Factors: 2 x 3 x 7 x 17
Number: 770    Factors: 2 x 5 x 7 x 11
Number: 780    Factors: 2 x 2 x 3 x 5 x 13
Number: 798    Factors: 2 x 3 x 7 x 19
Number: 840    Factors: 2 x 2 x 2 x 3 x 5 x 7
Number: 858    Factors: 2 x 3 x 11 x 13
Number: 870    Factors: 2 x 3 x 5 x 29
Number: 910    Factors: 2 x 5 x 7 x 13
Number: 924    Factors: 2 x 2 x 3 x 7 x 11
Number: 930    Factors: 2 x 3 x 5 x 31
Number: 966    Factors: 2 x 3 x 7 x 23
Number: 990    Factors: 2 x 3 x 3 x 5 x 11

[forta2k]

Thanks a lot.