Program to print non square numbers

0 0 8 minutes read

Write a program to print first n non-square number (non perfect square) .

Examples :

Input : 5
Output : 2 3 5 6 7

Input : 10
Output : 2 3 5 6 7 8 10 11 12 13

A naive method is to traverse all numbers from 1 to n. For every number, check if it is perfect square or not. If not a perfect square, print it.

C++

// CPP program to print first n
// non-square numbers.
#include <bits/stdc++.h>
using namespace std;
 
// Function to check perfect square
bool isPerfectSquare(int n)
{
    if (n < 0)
        return false;
 
    int root = round(sqrt(n)));
    return n == root * root;
}
 
// function to print all
// non square number
void printnonsquare(int n)
{
    // variable which stores the
    // count
    int count = 0;
    for (int i = 1; count < n; ++i) {
 
        // not perfect square
        if (!isPerfectSquare(i)) {
            cout << i << " ";
            count++;
        }
    }
}
int main()
{
    int n = 10;
    printnonsquare(n);
    return 0;
}

Java

// Java program to print first n
// non-square numbers.
import java.io.*;
import java.math.*;
 
class GFG {
     
    // Function to check perfect square
    static boolean isPerfectSquare(int n)
    {
       if (n < 0)
          return false;
     
       int root = Math.round((int)(Math.sqrt(n)));
       return n == root * root;
    }
     
    // function to print all
    // non square number
    static void printnonsquare(int n)
    {
        // variable which stores the
        // count
        int count = 0;
        for (int i = 1; count < n; ++i) {
     
            // not perfect square
            if (!isPerfectSquare(i)) {
     
                System.out.print(i + " ");
                count++;
            }
        }
    }
     
    // Driver code
    public static void main(String args[])
    {
        int n = 10;
        printnonsquare(n);
    }
}
 
 
/* This code is contributed by Nikita Tiwari.*/

Python3

# Python 3 program to print 
# first n non-square numbers.
import math
 
# Function to check perfect 
# square
def isPerfectSquare(n) :
     
    if (n < 0) :
        return False
 
    root = round(math.sqrt(n))
     
    return (n == root * root)
 
# function to print all
# non square number
def printnonsquare(n) :
     
    # variable which stores the
    # count
    count = 0
    i = 1
     
    while(count < n) :
     
        # Not perfect square
        if (isPerfectSquare(i)== False) :
            print(i, end =" ")
            count = count + 1
 
        i = i + 1
 
n = 10
printnonsquare(n)
 
# This code is contributed by Nikita Tiwari.

C#

// C# program to print first n 
// non-square numbers. 
using System;
 
class GFG
{
// Function to check perfect square 
static bool isPerfectSquare(int n) 
{ 
if (n < 0) 
    return false; 
 
double root = Math.Round((double )(Math.Sqrt(n))); 
return n == root * root; 
} 
 
// function to print all 
// non square number 
static void printnonsquare(int n) 
{ 
    // variable which stores the 
    // count 
    int count = 0; 
    for (int i = 1; count < n; ++i) 
    { 
 
        // not perfect square 
        if (!isPerfectSquare(i)) 
        { 
            Console.Write(i + " "); 
            count++; 
        } 
    } 
} 
 
// Driver code 
 
static public void Main ()
{
    int n = 10; 
    printnonsquare(n);
}
}
 
// This code is contributed by jit_t

PHP

<?php
// CPP program to print first
// n non-square numbers.
 
// Function to check 
// perfect square
function isPerfectSquare($n)
{
    if ($n < 0)
        return false;
 
    $root = round(sqrt($n));
    return $n == $root * $root;
}
 
// function to print all
// non square number
function printnonsquare($n)
{
    // variable which 
    // stores the count
    $count = 0;
    for ($i = 1; $count < $n; ++$i) 
    {
 
        // not perfect square
        if (!isPerfectSquare($i)) 
        {
            echo $i ." ";
            $count++;
        }
    }
}
 
// Driver Code
$n = 10;
printnonsquare($n);
 
// This code is contributed by mits.
?>

Javascript

<script>
 
// JavaScript program to print first n
// non-square numbers.
 
   // Function to check perfect square
    function isPerfectSquare(n)
    {
       if (n < 0)
          return false;
       
       let root = Math.round((Math.sqrt(n)));
       return n == root * root;
    }
       
    // function to print all
    // non square number
    function printnonsquare(n)
    {
        // variable which stores the
        // count
        let count = 0;
        for (let i = 1; count < n; ++i) {
       
            // not perfect square
            if (!isPerfectSquare(i)) {
       
                        document.write(i + " ");
                count++;
            }
        }
    }
       
 
// Driver code
 
        let n = 10;
        printnonsquare(n);
            
</script>

Output :

2 3 5 6 7 8 10 11 12 13

Time complexity : O(nlogn)
Auxiliary Space : O(1)
We can improve the above algorithm by using below formula
F(n) = n + floor(1/2 + sqrt(n))
By applying this function we get nth non square number.
Source and proof of the formula : Quora

Below is the implementation of above approach .

C++

// CPP program to print first n
// non square number
#include <bits/stdc++.h>
 
// Returns n-th non-square number.
int nonsquare(int n)
{
    return n + (int)(0.5 + sqrt(n));
}
 
void printNonSquare(int n)
{
    // loop to print non squares
    // below n
    for (int i = 1; i <= n; i++)
        printf("%d ", nonsquare(i));
}
 
int main()
{
    int n = 10;
    printNonSquare(n);
    return 0;
}

Java

// Java program to print first n
// non-square numbers.
import java.io.*;
import java.math.*;
 
class GFG {
     
    // Returns n-th non-square number.
    static int nonsquare(int n)
    {
        return n + (int)(0.5 + (Math.sqrt(n)));
    }
 
    static void printNonSquare(int n)
    {
        // loop to print non squares
        // below n
        for (int i = 1; i <= n; i++)
            System.out.print(nonsquare(i)+" ");
    }
 
    // Driver code
    public static void main(String args[])
    {
        int n = 10;
        printNonSquare(n);
    }
}
 
 
/* This code is contributed by Nikita Tiwari.*/

Python3

# Python 3 program to print
# first n non-square numbers.
import math
 
# Returns n-th non-square 
# number.
def nonsquare(n) :
     
    return n + (int)(0.5 + math.sqrt(n))
 
def printNonSquare(n) :
     
    # loop to print non
    # squares below n
    for i in range(1, n + 1) :
        print(nonsquare(i), end = " ")
 
n = 10
printNonSquare(n)
     
# This code is contributed by Nikita Tiwari.

C#

// C# program to print first n
// non-square numbers.
using System;
 
class GFG
{
     
    // Returns n-th non-square number.
    static int nonsquare(int n)
    {
        return n + (int)(0.5 + (Math.Sqrt(n)));
    }
 
    static void printNonSquare(int n)
    {
        // loop to print non squares
        // below n
        for (int i = 1; i <= n; i++)
            Console.Write(nonsquare(i)+" ");
    }
 
    // Driver code
    public static void Main()
    {
        int n = 10;
        printNonSquare(n);
    }
}
 
 
// This code is contributed 
// by Akanksha Rai(Abby_akku)

PHP

<?php
// PHP program to print first n 
// non square number
 
// Returns n-th non-square number.
function nonsquare($n)
{
    return $n + (int)(0.5 + sqrt($n));
}
 
function printNonSquare($n)
{
    // loop to print non squares
    // below n
    for ($i = 1; $i <= $n; $i++)
        printf(nonsquare($i) . " ");
}
 
// Driver Code
$n = 10;
printNonSquare($n);
 
// This code is contributed by mits
?>

Javascript

<script>
// Javascript program to print first n 
// non square number
 
// Returns n-th non-square number.
function nonsquare(n)
{
    return n + parseInt(0.5 + Math.sqrt(n));
}
 
function printNonSquare(n)
{
 
    // loop to print non squares
    // below n
    for (let i = 1; i <= n; i++)
        document.write(nonsquare(i) + " ");
}
 
// Driver Code
let n = 10;
printNonSquare(n);
 
// This code is contributed by gfgking.
</script>

Output:

2 3 5 6 7 8 10 11 12 13

Time complexity : O(nlogn)
Auxiliary Space : O(1)
An alternate solution is based on the fact that number of non-squares between two squares is always an even number.
Count of non-square numbers between two consecutive numbers k and k+1 is
= (k+1)² – k² + 1
= 2k
Count of non-squares between 1-4, 4-9, 9-16, … are 2, 4, 6, … respectively. These are even numbers.

Below is the implementation of the above approach.

C++

// CPP program to print first n
// non square number
#include <assert.h>
#include <math.h>
#include <stdio.h>
 
void printNonSquare(int n)
{
    int curr_count = 2, num = 2, count = 0;
    while (count < n) {
 
        // Print curr_count numbers. curr_count
        // is current gap between two square numbers.
        for (int i = 0; i < curr_count &&
                        count < n; i++) {
            printf("%d ", num);
            count++;
            num++;
        }
 
        // skip a square number.
        num++;
 
        // Count of next non-square numbers
        // is next even number.
        curr_count += 2;
    }
}
 
int main()
{
    int n = 10;
    printNonSquare(n);
    return 0;
}

Java

// Java program to print first n
// non-square numbers.
import java.io.*;
import java.math.*;
 
class GFG {
     
    static void printNonSquare(int n)
    {
        int curr_count = 2, num = 2, count = 0;
        while (count < n) {
     
            // Print curr_count numbers. curr_count is
            //  current gap between two square numbers.
            for (int i = 0; i < curr_count &&
                                count < n; i++) {
                                 
                System.out.print( num+" ");
                 
                count++;
                num++;
            }
     
            // skip a square number.
            num++;
     
            // Count of next non-square 
            // numbers is next even number.
            curr_count += 2;
        }
    }
 
    // Driver code
    public static void main(String args[])
    {
        int n = 10;
        printNonSquare(n);
    }
}
 
 
/* This code is contributed by Nikita Tiwari.*/

Python3

# Python 3 program to print
# first n non-square numbers.
import math
 
# Returns n-th non-square 
# number.
def printNonSquare(n) :
 
    curr_count = 2
    num = 2
    count = 0
 
    while (count < n) :
         
        # Print curr_count numbers. 
        # curr_count is current gap
        # between two square numbers.
        i = 0
         
        while(i < curr_count and count < n) :
             
            print(num, end = " ")
            count = count + 1
            num = num + 1
            i = i + 1
             
        # skip a square number.
        num = num + 1
 
        # Count of next non-square 
        # numbers is next even number.
        curr_count = curr_count + 2
 
n = 10
printNonSquare(n)
     
# This code is contributed by Nikita Tiwari.

C#

// C# program to print 
// first n non-square 
// numbers.
using System;
 
class GFG
{
static void printNonSquare(int n)
{
    int curr_count = 2, 
        num = 2, count = 0;
    while (count < n)
    {
 
        // Print curr_count 
        // numbers. curr_count 
        // is current gap between 
        // two square numbers.
        for (int i = 0; i < curr_count &&
                            count < n; i++) 
        {
            Console.Write(num + " ");
             
            count++;
            num++;
        }
 
        // skip a square number.
        num++;
 
        // Count of next 
        // non-square numbers
        // is next even number.
        curr_count += 2;
    }
}
 
// Driver code
static public void Main ()
{
    int n = 10;
    printNonSquare(n);
}
}
 
// This code is contributed 
// by akt_mit

PHP

<?php
// PHP program to print first n
// non-square numbers.
function printNonSquare($n)
{
    $curr_count = 2; $num = 2; $count = 0;
    while ($count < $n) 
    {
 
        // Print curr_count numbers. curr_count is
        // current gap between two square numbers.
        for ($i = 0; $i < $curr_count &&
                          $count < $n; $i++)
        {
            echo($num . " ");
             
            $count++;
            $num++;
        }
 
        // skip a square number.
        $num++;
 
        // Count of next non-square 
        // numbers is next even number.
        $curr_count += 2;
    }
}
 
// Driver code
$n = 10;
printNonSquare($n);
 
// This code is contributed by Mukul Singh. 
?>

Javascript

<script>
 
// Javascript program to print first
// n non-square numbers.
function printNonSquare(n)
{
    let curr_count = 2, num = 2, count = 0;
    while (count < n)
    {
         
        // Print curr_count
        // numbers. curr_count
        // is current gap between
        // two square numbers.
        for(let i = 0; 
                i < curr_count && count < n; 
                i++)
        {
            document.write(num + " ");
 
            count++;
            num++;
        }
 
        // Skip a square number.
        num++;
 
        // Count of next
        // non-square numbers
        // is next even number.
        curr_count += 2;
    }
}
 
// Driver code
let n = 10;
 
printNonSquare(n);
 
// This code is contributed by decode2207
 
</script>

Output:

2 3 5 6 7 8 10 11 12 13

Time complexity: O(n²) since while loop will run for n times and inner while loop will also run for n times

Auxiliary Space: O(1) because using constant variables only

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!