DEV Community

Cover image for Monday Express BigO Notation [Day 1]
Cliff Gor
Cliff Gor

Posted on • Edited on

Monday Express BigO Notation [Day 1]

Hello welcome to the first BigO notation challenge where we will be solving a few challenges 🚀

For our first challenge we are going to solve this problem, feel free to use any language that you are comfortable with.

Big O Challenge Link

A prime is a natural number greater than that has no positive divisors other than and itself. Given integers, determine the primality of each integer and print whether it is Prime or Not prime on a new line.

Note: If possible, try to come up with an primality algorithm, or see what sort of optimizations you can come up with for an algorithm. Be sure to check out the Editorial after submitting your code!

Function Description

Complete the primality function in the editor below. It should return Prime if is prime, or Not prime.

primality has the following parameter(s):

  • n: an integer to test for primality

Input Format

The first line contains an integer, , denoting the number of integers to check for primality.

Each of the subsequent lines contains an integer, , the number you must test for primality.

Constraints

Output Format

For each integer, print whether is Prime or Not prime on a new line.

Sample Input

3
12
5
7

Enter fullscreen mode Exit fullscreen mode

Sample Output

Not prime
Prime
Prime

Enter fullscreen mode Exit fullscreen mode

Explanation

We check the following integers for primality:

  1. is divisible by numbers other than and itself (i.e.: , , , ), so we print Not prime on a new line.
  2. is only divisible and itself, so we print Prime on a new line.
  3. is only divisible and itself, so we print Prime on a new line.

I hope to see all those responses and if you can do a video solving the solution.

Good Luck 🎉

Top comments (3)

Collapse
 
miami profile image
Larry Miami

Done!I have 3 evaluations at first "n==1 (not prime) or if n==2 (for even numbers) and (n%2)==0, if this is true, returns 'Not prime'."Then we loop from 3 to sqrt(n),counter i increases by 2 because we don't have to check for even numbers.And if n% counter i == 0 the number is not a prime.After all the evaluations,we are left with prime numbers,does that make sense?

function primality(n) {

    if((n==1)|(n%2)==0 && n!=2 ){
        return 'Not prime';
    }

    for(let i = 3; i<=Math.sqrt(n);i+=2){
            console.log(i);
            if((n%i)==0){
                return 'Not prime';
            }
    }

    return 'Prime';

}

Collapse
 
cliffgor profile image
Cliff Gor

awesome Miami Larry for this awesome explanation of your solution

Collapse
 
claudwatari95 profile image
ClaudWatari • Edited

Here, we start by checking if the number is equal to 1, since we know 1 is not a prime number, we return and exit from the function.
We then loop from integer 2 and exit at integer n and check if current value of n is divisible by current iterator value, which means it is not a prime number. Otherwise, it is a prime number.
Of course, we started off by ensuring that n is an integer, by checking it's data type.

EDIT: **Cannot figure out why screenshot is not uploading, so I've pasted my code instead.

const primality= (n) => {
if(typeof n !== 'number') return 'Must be a number'
if(n === 1) return 'Not prime'
for(var x = 2; x < n; x++)
if(n % x === 0) return 'Not prime';
return 'prime';
};

console.log(primality(3));
console.log(primality(12));
console.log(primality(5));
console.log(primality(7));