Answer 1

Good one. Manav Roy and
Your questions always in trending 🔥

You can further reduce your code to simply :
//not checking numbers 1 and itself.

#include <iostream>
using namespace std;

int main() {
int n;
cin>>n;
int n2=n/2;

for(;n2>1;n2--){
if(n%n2==0)
{
cout<<"Composit"<<endl;
break;
}
}

if(n2==1)
cout<<"Prime"<<endl;

return 0;
}

//further you can reduce complexity by n2 = sqrt(n) ; factors exist between 2 to sqrt(n) if any.
you can skip even numbers check also.

Hope it helps...

Answer 2

When 6%5 != 0 is true, so isPrime= true is set so it prints 1

Manav Roy
you can't say "not divisible by 2 or 3 or 5 " is a prime.

Answer 3

G'day Manav Roy when you are ready, we can help you to optimise your algorithm. Post your revised code here please?

Answer 4

HungryTradie oh you wanna say that he's to only check from 1 to n/2 right?

Answer 5

https://code.sololearn.com/c2vxrGZw8b23/?ref=app

Answer 6

Your code runs fine but the logic is wrong. You've to check the divisibility of every number from 1 to n, if the total numbers that divide it is 2(1 and the number itself), then it's prime. Else it's not a prime number. Your code doesn't work because there are some non-prime numbers that aren't divisible by 2, 3 or 5(am i right in this point? If no, give an example for such a number)

Answer 7

Frankly I think it's not so simple.
Take the case of 17,19 and 43.
These are primes. And what about composite primes ?
Remember 1 is not a prime.(forget Prime Minister).
Looping works but the depth of search is proportional to the size of the input..(think of the impact of very large numbers).

Answer 8

Sanjay Kamath -1?

Answer 9

Like this Raul Ramirez ?

Hint, input a 5 digit number on the first run so SoloLearn gives it extra time on the next run. Up to 150901 for now, but I think I can reduce complexity further.

https://code.sololearn.com/crJ7V7Yd7WsT/?ref=app

Answer 10

Manav Roy You're welcome...

Answer 11

Prime number have factors 1 and itself only..
2 have 1,2
3 have 1,3
5 have 1,5
But 6 has 1,2,3,6 so its not prime..

So you need find is there any factors from 1 to N, if any other than 1,N its not prime. If it only have those 2 factors, its a prime.. Hope you got logic.. Use a loop.. And try to find factors..

Answer 12

Manav Roy 1 is neither prime nor composite 😅 Yes / and so is ZERO...:-)

Answer 13

It is same as we start checking from 2 to that number.
But it doesn't matters at all we have to reduce the time complexity.

Answer 14

Manav Roy

Point one, you understand, to which number we can call it as prime.

So, when a number have atleast two factors, it is said to be a prime number.
If any number that can have minimum three factors called as composite number.

Here factor is a number where it exactly divides the main number.

Example:
Let's check with 21,
Step 1. Factors of 21 are 1, 3, 7, 21
Step 2. Counting number of factors, for 21, 4 factors
Step 3. As number of factors greater than 2, it is composite. If in case the number have 2 factors, then the number is prime.

In C++;

#include<iostream>
using namespace std;
int main(){
int i, num,count =2; //as 1 and number itself are factors.
cin>>num;
for(i=2;i<num/2;i++){
if(num%i==0){
count++;
}
}
if(count==2)
cout<<"Prime";
else
cout<<"Composite";

return 0;
}

https://code.sololearn.com/cqA2yGoiwHp8/?ref=app

Answer 15

You have to check if every number, up to its sqrt, doesnt factor into it

As soon as one does its not a prime

Answer 16

Linearly you loop from n = 1 to n for n factors..
Ex : for 10 : 1,2,5,10
For 30 : 1,2,3,5,6,10,15,30

Observe, you don't need to check 1,itself. And you don't factors above n/2 to n-1 ie (5 to 10 , and 15 to 30) so you can skip numbers to check n/2 to n so run loop only from n2/2 to 1 instead of n2 to 1. It skipping n/2 numbers check which are not needed actually...

Additionally, did you observed,
For 10 : 1,2,5,10
10%1 => 1*10
10%2 => 2*5
10%5 => 5*2
10%10 => 10*1
It's a repeated check, for 5,10 so factor exits between 2 to sqrt(n) , if any. So here 2 to sqrt(10) => almostly 2 to 3 is enough to check is it factors exits or not.
Its about how many times loop repeating.. Increasing iterations mean increasing complexity ..
Not value n which you checking isPrime?

Hope it clears...

....

Answer 17

77

Answer 18

Um...no, 77 isn't a prime. It has 1, 7, 11, 77 as factors so it isn't a prime. A prime number has only it's self & 1 as factors.

Answer 19

143 is 11*13.
want me to post 13*17 next? or 17*23?

{Edit: oops, I forgot 19.
but the point is: you need to check from i=2 to i*2<=n}

{Edit2: I've got some more tricks for another time, so far I can get SoloLearn to run to 6 digits of primes before timeout for C language. 145603 is a prime.}

{edit3: so is 150217}

Answer 20

G'day Manav, yes, but you don't check down to 0. Instead check up from 2 to n/2. If you use range i:2 to n/2, check if n%i==0 true number n is composit.

n/2 has to be <= the biggest factor because the other factors you need to check would themselves get multiplied by n/3, or n/4, or n/5 etc until you reach n/n.
If the smallest factor (except for 1) is 2, that means the biggest factor (except n it's self) that can ever be a factor of number n is n/2.
After 2 the next smallest is the next prime, so check %3. After that, 4 already has 2 as a factor (and you have already checked %2 so no need to check %4). Next smallest prime is 5, but it would have to be multiplied by <= n/5.

A bit of math gives you:
5/1 = n/5
Multiply both sides by 5 gives you 25/1=n divide both sides by n gives 25/n =1, and we know 25 is 5².
So both 5 and n/5 would have to be <= sqrt of n.

That means instead of checking to n/2 we can check to sqrt(n). The easiest way to do that is make the condition of your for loop be i*i<=n.