1,105,169 Community Members

c++ Prime Number problem

Member Avatar
mikeshadow
Newbie Poster
7 posts since Jan 2012
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

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

Member Avatar
thines01
Postaholic
2,420 posts since Oct 2009
Reputation Points: 389 [?]
Q&As Helped to Solve: 413 [?]
Skill Endorsements: 10 [?]
Team Colleague
Featured
 
0
 

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

Member Avatar
mikeshadow
Newbie Poster
7 posts since Jan 2012
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
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.

Member Avatar
frogboy77
Posting Pro in Training
477 posts since Aug 2010
Reputation Points: 73 [?]
Q&As Helped to Solve: 43 [?]
Skill Endorsements: 1 [?]
 
0
 

you could try a sieve

Member Avatar
rohan121212
Light Poster
26 posts since Nov 2011
Reputation Points: -4 [?]
Q&As Helped to Solve: 3 [?]
Skill Endorsements: 0 [?]
 
-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");
}
Member Avatar
LRRR
Junior Poster in Training
55 posts since Dec 2011
Reputation Points: 9 [?]
Q&As Helped to Solve: 15 [?]
Skill Endorsements: 0 [?]
 
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.

Member Avatar
rohan121212
Light Poster
26 posts since Nov 2011
Reputation Points: -4 [?]
Q&As Helped to Solve: 3 [?]
Skill Endorsements: 0 [?]
 
-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

Member Avatar
zeroliken
Nearly a Posting Virtuoso
1,222 posts since Nov 2011
Reputation Points: 79 [?]
Q&As Helped to Solve: 216 [?]
Skill Endorsements: 15 [?]
 
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

Member Avatar
mikeshadow
Newbie Poster
7 posts since Jan 2012
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
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

Member Avatar
NathanOliver
Posting Virtuoso
1,657 posts since Apr 2009
Reputation Points: 284 [?]
Q&As Helped to Solve: 310 [?]
Skill Endorsements: 4 [?]
 
1
 

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

Member Avatar
WaltP
Posting Sage w/ dash of thyme
9,363 posts since May 2006
Reputation Points: 2,905 [?]
Q&As Helped to Solve: 1,151 [?]
Skill Endorsements: 45 [?]
Team Colleague
 
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.

Member Avatar
Caligulaminus
Junior Poster
106 posts since Feb 2011
Reputation Points: 35 [?]
Q&As Helped to Solve: 30 [?]
Skill Endorsements: 0 [?]
 
1
 

And what the heck is 50????

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

Member Avatar
Lerner
Nearly a Posting Maven
2,416 posts since Jul 2005
Reputation Points: 579 [?]
Q&As Helped to Solve: 407 [?]
Skill Endorsements: 16 [?]
 
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.

Member Avatar
jaskij
Junior Poster
105 posts since Oct 2011
Reputation Points: 45 [?]
Q&As Helped to Solve: 19 [?]
Skill Endorsements: 0 [?]
 
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.

Member Avatar
mikeshadow
Newbie Poster
7 posts since Jan 2012
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
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

You
This article has been dead for over three months: Start a new discussion instead
Post:
Start New Discussion
View similar articles that have also been tagged: