CareerCup

Find all prime No less than n/2.
Print only those pair of found prime No. whose product is less than n

void printLessThanPrimeset(int n){
if (n<4) return;
for (int i=2; i<n; i++){
if (isPrime(i)){
for (int j=n/i; j>=2; j--){
if (isPrime(j)){
cout << i << "x" << j << "=" << i*j << "<=" << n << endl;
}
}

}
}
return;
}

bool isPrime(int n){
if (n==1) return false;
if (n==2) return true;

for (int i=2; i<n; i++){
if (n/i-double(n)/double(i)==0) return false;
}
return true;

}

What does "pair" mean? |p-q| = 2 ?

You can sieve out composites from [2,n], then print pairs.

UPDATE====
Oh wow down vote makes me cry so hard :)
Yeah it says p*q <=n, not p, q <=n , misread.

So you can save on the range [2,n].

And only consider [2, n/2] to sieve on.

Let the OP just do it on [2,n] as a first coding step (his/her final check on pq <=n will take care of correctness). Can someone explain to him why n/2, as I will now:

Because , the boundary/extreme case is:
------------------------------------------------------

(smallest possible prime)*(largest possible) <=n

And (smallest possible prime) = 2, so:

2*(largest possible prime) <=n

which implies (divide both sides by 2):

(largest possible prime) <= n/2

Anyone care to explain the complexity of this algorithm?

How does this question is different from finding out the prime numbers till n/2.
2×q<=n
So 2<q<=n
So it boils to finding prime numbers from 2 to n/2.

k

private void printPrimePairs(int N) {
		if (N <= 5)
			System.out.println("No Pairs exist");

		for (int i = 2; i <= (N / 2); i++) {
			if (isPrime(i)) {
				for (int j = i + 1; j <= (N / 2); j++) {
					if (isPrime(j) && (i * j) <= N) {
						System.out.println(i + " " + j);
					}
				}
			}
		}
	}

	private boolean isPrime(int i) {
		int j = 2;

		if (i == 2)
			return true;

		while (j < i) {
			if (i % j == 0) {
				return false;
			}
			j++;
		}
		return true;
	}

// find all pairs of p,q prime numbers such that p * q <= n

// find all prime numbers < = n / 2
// find pairs of prime numbers that satisfy the condition from earlier collected numbers

bool isPrime(int n)
{
	if (n <= 1)
		return false;
	
	if (n == 2)
		return true;
	
	if(n > 2 && n %2 == 0)
		return false;
		
	for(int i = 3; i < n / 2; i += 2)
	{
		if(n % i == 0)
			return false;
	}
	return true;
}

void printPairs(int n)
{
	vector<int> primes;
	for(int i = 1; i <= n; i++)
	{
		if(isPrime(i))
			primes.push_back(i);
	}
	for(int i = 0; i < primes.size(); i++)
	{
		for(int j = 0; j < primes.size(), i != j; j++)
		{
			if(primes[i] * primes[j] <= n)
			{
				cout<<primes[i]<<" "<<primes[j]<<endl;
			}
		}
	}
}

bool isPrime(unsigned int n, vector<unsigned int> &primes) {

   for(auto iter i = primes.begin() ; i!= primes.end() ;++i) {
       if ( ! n%*i ) return false;
   }

   return true;
}

void findPairs(const uint n, set<pair<unit,unit>> &products) {

   vector<unsigned int> &primes ;

   for(uint i = 2 ; i<= n/2 ; ++i) {
      if( isPrime(i, primes)) 
        primes.puch_back(i);
   } 


   for(vector<uint>::reverse_iterator iter i=primes.end() ; i!= primes.begin() ;++i) {
          for(vector<uint>::iterator iter j=primes.begin() ; j!= primes.end() ;++j) {
                  if( *i* *j == n && products.find(make_pair<*j,*i>) == products.end() ) { 
                            products.insert( make_pair(*i,*j) );
                  }
                  if (*i * *j > n) continue;
          }
    }

}

static bool IsPrime(int n)
        {
            int limit = (int)Math.Sqrt(n) + 1;
            for (int i = 2; i < limit; i++)
            {
                if (n % i == 0)
                {
                    return false;
                }
            }
            return true;
        }

        static void SearchPrimePairs(int n)
        {
            for (int i = 2; i < n / 2 + 1; i++)
            {
                if (IsPrime(i))
                {
                    for (int j = 2; j < n/i + 1; j++)
                    {
                        if (i * j <= n)
                        {
                            if (IsPrime(j))
                            {
                                Console.WriteLine("{0}:{1}", i, j);
                            }
                        }
                    }
                }
            }
        }

//C# with a little improvement (taking primes out and reusing in IsPrime) to Dave's C++ code 
// find all pairs of p,q prime numbers such that p * q <= n
// find all prime numbers < = n / 2
// find pairs of prime numbers that satisfy the condition from earlier collected numbers
private static ArrayList primes;

static bool isPrime(int n)
{
	if (n <= 1)
		return false;

	if (n == 2)
		return true;

	foreach (int i in primes)
	{
		if (n % i == 0)
			return false;
	}
	return true;
}

static void printPairs(int n)
{
	primes = new ArrayList();
	primes.Clear(); //Remove all elements from the ArrayList. This could be improved to remove elements larger than n/2 if needed
	int max = n / 2; //for performance
	for (int i = 1; i <= max; i++)
	{
		if (isPrime(i))
			primes.Add(i);
	}
	foreach (int i in primes)
	{
		foreach (int j in primes)
		{
			if (i * j <= n)
			{
				Console.WriteLine(String.Format("({0}, {1})", i, j));
			}
		}
	}
}

Use the Eratosthene's sieve algorithm only as URIK LAGNES suggested. Just find primes from 1 to sqrt(N) store them in a set.
All pairs from this set should be printed as answers.