c++ Prime Number problem

[mikeshadow]

I need an algorithm that finds how many prime numbers are in a set interval; the interval maximum range is 1 000 000 so a brute force method of checking every number is kinda inefficient

[thines01]

Have you done a search for the phrase prime number on this site?
You can find a multitude of examples in multiple languages.

[mikeshadow]

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.

[frogboy77]

you could try a sieve

[rohan121212]

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");
}

[LRRR]

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.

[rohan121212]

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

[zeroliken]

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

[mikeshadow]

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

[NathanOliver]

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

[WaltP]

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.

[Caligulaminus]

And what the heck is 50????

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

[Lerner]

>>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.

[jaskij]

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.

[mikeshadow]

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