prim numbers-output

[enemy]

Hello!
I wanted the program telling if the number is a prime number or not.
Then, I also wanted, if the number is NOT prime, the program to write out at least one other prime number we can devide it by.

F.e, if we imput 119, I wanted at least 7 to be written out.

Here is what I tried:

//prime numbers

#include<iostream>
using namespace std;



bool Prime (const int st) {

for (int i=2; i<st; i++){
if (st%i==0)
cout << i<<endl;
return false;

}
return true;


}
int main(){
int a=119;
bool b = Prime(a);
cout << b;
return 0;
}

Many thanks!

[ne555]

¿what is the problem?
Indent your code properly.

[condor]

Besides indentation, I think that the bool function should be rewritten.

[enemy]

I want the program to write i , but it doe s not.

For a=119

I get only :
2
3
4
5
6

what sinn have these numbers? That was the output of thta what U see up !

[enemy]

This code gives output:

2
3
4
5
6
false

[code#include<iostream>
using namespace std;



bool jePra (const int st) {

for (int i=2; i<st; i++){
if (st%i==0)

return false;
cout <<i <<endl;
}
return true;


}
int main(){
int a=119;
bool b = jePra(a);
cout << b;
return 0;
}][/code]

[enemy]

And the FIRST code, where cout<<i<<endl, is BEFORE return false; has just output: false.


I do not understand.
Please,can someone help?

[condor]

Try this function:

bool Prime (const int st)
{
	bool answer = true;
	
	for (int i = 2; i < st; i++)
		if (st % i == 0)
		{
			cout << i << endl;	// it prints out the first prime divisor
			answer = false; 	// the number is not prime
			break;			// no need to continue the for loop
		}
	return answer;
}

[enemy]

:tup

Why do I have to have st as a CONSTANT?
What would happen if I would not?

Many thanks!

[condor]

It can be also int, not necessarily be const.

The for loop: in fact, the loop should have the upper limit equal to the square root of the number. Guess the reason!

[condor]

@enemy

If you consider all OK, please mark this thread as Solved.

[enemy]

Hello, Condor!
If we check if is a prime number or not ,

\squrt(77)= 8...
77=7*11
8>7

\\sqrt(119)=10...

119=7*17
7<10

itn

Square root from each number is really bigger then the first prime divisor, bt sqrt is sqrt and divisors are divisors, integers, so how can we connect it loggiclaly and see it in advance as a general rule?

Many thanks!

But how do we see it on eyes for general?
Many thanks!

[condor]

OK. square root of 77 is greater than 8 and but we will take (int)sqrt(77).

Generally speaking, if a number n is not prime then it has necessarily a prime divisor d₁ <= sqrt(n) who has a "pair" d'₁ = n / d₁ >= sqrt(n).

More than that, if n is a perfect square then one of the divisors will be d_i = sqrt(n) and d'_i = n / d_i = sqrt(n) as his "pair". In such cases d'_i = d_i

We may therefore look for divisors between sqrt(n) and n, but there are more numbers in that interval and the for loop will be "longer".

So, when we're looking for divisors of n it is enough to seek up to the sqrt(n).

[enemy]

Thanks condor, just digested it!
if n=a*b and a<b, then a^2 should be < then n^2 and sqrt(n) should be >a.
Please,

what is the line:
bool answer= true;

meaning for the COMPILER?
Does it mean that we "set" the value to "true", EXCEPT in the for loop condition, where it is changed to "false",?

Many thanks!

[condor]

OK, that line is to define and initialize the bool variable as true. When in the for loop the expression st % i == 0 is true then, obviously, answer = false (the number is not prime) and break; will stop the loop. That's all.

[enemy]

Thanx!
Please, if I try that version You said, to try with sqrt(st), how do I cout out the sqrt?

I tried like this, but it seems to be many unclear thhings in there:

#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;


bool Prime (int st2)
{
	bool answer = true;                       
	
	for (int i = 2; i < st2; i++)
		if (st2 % i == 0)
		{
			cout <<"Write first prime divisor " <<i << endl;	
			answer = false; 	
			break;			
		}
	return answer;
}

int main(){
double st, m;
cout<<"Write  number you wannna tes.";
cin>>st;

m=sqrt(st);
double st1;
st1=printf("sqrt(%f)=%f\n", st, m);

int st2=(int)st1;





cout<<Prime(st2);
cout<<st1;
system("PAUSE");
return 0;
}

[enemy]

After the line printing the sqrt, in the next line I always get a number which is either 25 or 27, and have no idea what it is and how it appears!


Please, can someone help?
Many thanks!

[condor]

Please, if I try that version You said, to try with sqrt(st), how do I cout out the sqrt?

Here's the loop as I said above with the upper limit equal with sqrt(st):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

#include<iostream> using namespace std; bool Prime (int st) { bool answer = true; for (int i = 2; i <= sqrt(st); i++) if (st % i == 0) { cout <<"First prime divisor " << i << endl; answer = false; break; } return answer; } int main() { int st; cout<<"Write number you wannna tes.: "; cin>>st; cout<<Prime(st); cin.get(); return 0; }

Write number you wannna tes.: 119 Write first prime divisor 7 0 Write number you wannna tes.: 169 Write first prime divisor 13 0 Write number you wannna tes.: 67 1

[condor]

@enemy

If you consider all OK, please mark this thread as Solved.

[Chervil]

Line 9 for (int i = 2; i <= sqrt(st); i++) is probably inefficient. I don't think the compiler can optimise this, so the function call to sqrt() is re-executed on each iteration. It's safer in terms of efficiency to calculate and store the sqrt() before the start of the for loop, and test against the stored value.

[condor]

OK, Chervil, thank you very much!

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

#include <iostream> #include <cmath> using namespace std; bool Prime (int st, int sqr) { bool answer = true; for (int i = 2; i <= sqr; i++) if (st % i == 0) { cout <<"Write first prime divisor " <<i << endl; answer = false; break; } return answer; } int main() { int st; cout<<"Write number you wannna tes.: "; cin>>st; int sqr = sqrt(st); cout<<Prime(st, sqr) << endl; cin.ignore(); cin.get(); return 0; }

Write number you wannna tes.: 119 Write first prime divisor 7 0 Write number you wannna tes.: 169 Write first prime divisor 13 0 Write number you wannna tes.: 67 1