So I accidentally posted this is the wrong forum. Anyway, I'll post it here again because the other one should be deleted.
I need to write a program that gets an integer 'n' as input and outputs all of the odd primes less than or equal to 'n'. This is what I currently have:
#include<iostream>
usingnamespace std;
int main(){
int num;
bool prime;
cout << "Please enter a positive integer" << endl;
cin >> num;
for(int i = 3; i <= num; i++){
prime = true;
for(int n = 2; n <= i - 1; n++){
if(i % n == 0){
prime = false;
}
}
if(prime){
cout << i << " is prime" << endl;
}
}
return 0;
}
Now whilst this works, it runs slowly when calculating with large numbers. What I'd like to do is use some while loops and make it run more efficiently. Any help anyone could offer would be greatly appreciated.
If you don't mind storing the prime numbers in an array during the calculation, you could print them all out at the end, and speed up the overall process as well. No reason to check if a number is divisible by 10 when you've already seen that it isn't divisible by 2 and 5, etc.
So store all the prime numbers you have discovered in an array, and check the next integer only with the entries in the array, and only those less than or equal to the square root of the integer you're checking.
Here is a really efficient way to check if a number is prime. I took this out of my program that is currently running to see how many prime numbers are in a googol.
Btw, I'm also trying to find someone to make this more efficient.
#include "stdafx.h"
#include <math.h>
#include <iostream>
usingnamespace std;
usingnamespace System;
int IS_prime(double num); // Returns '0' if its prime, and a '1' if its not prime.
int IS_prime(double num)
{
int isprime = 0;
for(int i = 2; i <= sqrt(num); i += 2)
{
if(i % 2 == 0)
i++;
if((int(num)% i) == 0)
{
isprime = 1;
break;
}
}
return isprime;
}
First of all, I would not define a function to check a floating-point number whether it is a prime, as a prime is always an integer.
Next, I would not use down-casting for double number to int number as it would lose the actual value.
And finally, your progam is not right. Check it out with inputting a value 1234567890 which your program states is a prime number
Doom:
Here the most efficient (I could come up with) way of checking a prime number.
#include <iostream>
using namespace std;
//using namespace system;
int isPrime(long num) // Returns 1 (true) if its prime, or 0 (false) if not
{
if (num < 2) // 1 is not a prime number
return 0;
// if it is > 2 and an even number, then it definitely is not a prime
if (num > 2 && (num % 2) == 0)
return 0;
//considering the fact all can be divided by 1 and itself,
//start checking if there is any other divisor, if found one then no need to continue, it is not a prime
for(int i = 2; i < num; i++ )
{
cout << " divisor: " << i << endl;
if ( (num % i) == 0) // if it is divisible by i
{
// a divisor other than 1 and the number itself
return 0; // no need for further checking
}
}
return 1; // if all hurdles/checks are crossed, heyyyy, its a prime
}
int main()
{
int num;
do {
cout << " enter a number (0 to stop) " << endl;
cin >> num;
if (num) {
if (isPrime(num))
cout << num << " is a prime numebr " << endl;
else
cout << num << " is NOT a prime numebr " << endl;
}
} while (num > 0);
return 0;
}
This one loops utmost 9 times to check if any given number is a prime.
Any number should come out with a divisor 1 to 9 (I guess any number).
Hence the maximum number of iterations it takes to check if given number is a prime, is 9 times.
I guess that is most efficient and quickest loop to check.
#include<iostream>
#include<cstdlib>
usingnamespace std;
int main(){
int num, numprimes = 1;
int *primes,*temp; // i'm not sure if temp will be necessary to prevent memory leaks maybe someone could tell me
bool prime;
primes = (int*)malloc(1*sizeof(int));
primes[0] = 2;
cout << "Please enter a positive integer" << endl;
cin >> num;
for(int i = 3; i <= num; i++){
prime = true;
for(int n = 0; n < numprimes; n++){
if(i % primes[n] == 0){ /* if it is divisible by a compound number, then it was definitely divisible by a lesser prime.
why bother with compounds? */
prime = false;
break; // this might also speed things up
}
}
if(prime){
cout << i << " is prime" << endl;
temp = (int*)realloc(primes,(++numprimes)*sizeof(int));
if(temp != primes) free(primes);
primes = temp;
primes[numprimes-1] = i;
}
}
return 0;
}
This one might take longer to find all the primes below the input for smaller inputs, but for greater inputs, it will be much faster. For really large numbers you might want to write them to a file. If you think this is fast enough, as i do, then you may leave out the bit about square roots; sqrt() itself isn't so fast a function. But then, for REALLY large numbers, it may be useful.