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 squarebool isPerfectSquare(int n){ if (n < 0) return false; int root = round(sqrt(n))); return n == root * root;}// function to print all// non square numbervoid 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 # squaredef isPerfectSquare(n) : if (n < 0) : return False root = round(math.sqrt(n)) return (n == root * root)# function to print all# non square numberdef 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 + 1n = 10printnonsquare(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 squarefunction isPerfectSquare($n){ if ($n < 0) return false; $root = round(sqrt($n)); return $n == $root * $root;}// function to print all// non square numberfunction 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 = 10printNonSquare(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 Codelet 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)2 – k2 + 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 + 2n = 10printNonSquare(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 codestatic 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 codelet 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(n2) 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
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
