Start New Discussion within our **Software Development Community** Not Yet Answered # c++ Prime Number problem

thines01 389 Discussion Starter mikeshadow rohan121212 -4 LRRR 9 rohan121212 -4 zeroliken 79 Discussion Starter mikeshadow Featured Reply NathanOliver 429 Featured Reply WaltP 2,905 Caligulaminus 35 Lerner 580 jaskij 45 Discussion Starter mikeshadow

0

Have you done a search for the phrase prime number on this site?

You can find a multitude of examples in multiple languages.

0

I have read every example and they only provided me with optimizations but not the result itself what I'm looking for is an algorithm that can run in less than 0.1 sec.

-3

try this

```
#include<iostream>
using namespace std;
main()
{
int n,k,l;
k=8;
l=4;
cout<<"Enter thenumber till the check should go";
cin>>n;
for(int i=7;i<n;i++)
{
if ((k%2!=0)&&(k%3!=0)&&(k%5!=0)&&(k%7!=0))
{l++;}
k++;
}
cout<<"\n"<<l;
system("pause");
}
```

0

Avoid that code above. First of all it doesn't work at all, aside from that, main has no return type, and has no return value either, and that's bad, very bad. Using system("pause") is also not recommended, use cin.get() instead.

`if ((k%2!=0)&&(k%3!=0)&&(k%5!=0)&&(k%7!=0))`

This statement only checks if a number can be divided by 2, 3, 5, 7. I can easily make up numbers that are not primes yet cannot be divided by 2 3 5 7. In fact any multiplication of prime numbers above 7 will be missed. Starting from 11, the wider the range the more you miss.

11 * 11 = 121

11 * 13 = 143

11 * 17 = 187

13 * 17 = 221

17 * 17 = 289

23 * 11 = 253

23 * 17 = 391

23 * 23 = 529

29 * 11 = 319

29 * 13 = 377

29 * 17 = 493

As thines01 indicated there are probably hundreds of threads about finding prime numbers already, try to do some search. I am sure you will find something useful.

-5

who told you that 121 is a prime number oh please

besides the code i have written works perfectly fine and i have tested it a hundred times

and i can pretty easily guess that you are a noob at c++ as this code is made for dev c++ compiler which is popular nowadays

0

who told you that 121 is a prime number oh please

besides the code i have written works perfectly fine and i have tested it a hundred times

Please be reminded that the code you post should always be compatible with different (if not all) compilers

for example main should have a return type ..int to be exact

i can pretty easily guess that you are a noob at c++ as this code is made for dev c++ compiler which is popular nowadays

Keep it pleasant, don't be rude to other members, also I can say that he knows what he's talking about and is quite knowledgeable at c++ as i have seen his previous posts

0

seeing as this prime number method is not useful, i will post the problem's original content : in the interval [x,y] how many numbers have exactly 14 divisors? y can go up to 64000000

1

So what you need is more like prime factorization. There are many threads on this site that talk about that.

1

who told you that 121 is a prime number oh please

If it did anything useful, *your program* would...

besides the code i have written works perfectly fine and i have tested it a hundred times

Really? I entered 130 and it output 32. How is that useful?

I added a cout to display the prime numbers it calculates and got

```
Enter thenumber till the check should go200
11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89
97 101 103 107 109 113 [B]121[/B] 127 131 137 139 [B]143[/B] 149 151 157 163
167 [B]169[/B] 173 179 181 [B]187[/B] 191 193 197 199
50Press any key to continue . . .
```

Where's 2, 3, 5, and 7? What is 121, 143, 169, and 187 doing in the list? And what the heck is **50**????

It runs fine, but the answers are completely wrong... Therefore it's useless.

1

And what the heck is

50????

The number of rohan-primes between 0 and 200. :icon_mrgreen:

0

>>in the interval [x,y] how many numbers have exactly 14 divisors

24 has 16 integer divisors: 24, 1, 12, 2, 8, 3, 6, 4 (and respective negative ints)

24 has 8 positive integer divisors

24 has 2 prime divisors: 2 and 3, assuming the definition of prime divisors is divisors that are prime (and if you accept the definition that 1 isn't a prime number).

I know of no short cut way to determine the number of postive integer divisors a number has, except to say if the number is prime, then the number of divisors is 2. Maybe someone is aware of a nifty algorhithm to determine the number of positive integer divisors any given positive integer has. I'd use brute force.

0

Mark me wrong, but a sieve for 8k numbers shouldn't run too long.

Why 8k? It's sqrt(64000000) and all divisors are mirrored after square root, ie:

Divisors of 28: 1,2,4,7,14,28. You can connect them in pairs: 1-28,2-14,4-7. And guess what? Left and right sides of the pair are parted by sqrt(28).

To make myself clear: if you want exactly 14 divisors (are they proper?) of a number, just check, if there are exactly seven divisors <sqrt(number).

At this point, all you need to do is make some optimalizations, like if a number is a square of an integer, there is a connection between it's and it's sqrt's divisors and so on.

0

actually that is partly incorrect because for a number to have 14 divisors it must be of this form : p1*p2^6 where p1 and p2 are prime numbers i have tried setting an upper and bottom limit for p2 and analyzing the prime numbers but it too slow

This article has been dead for over six months. Start a new discussion instead.