LinuxQuestions.org
Latest LQ Deal: Latest LQ Deals
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 10-26-2005, 12:14 PM   #16
dmail
Member
 
Registered: Oct 2005
Posts: 970

Rep: Reputation: Disabled

[QUOTE]Originally posted by lmvent
Code:
    int n = (int)sqrt(static_cast<float>(maxN));
    vector<int>primes;
    for(int i = 2; i <= n ; i = i + 1)
    {   primes.push_back(i);
        for(int j = 2; j <= (int)sqrt(static_cast<float>(n)) && j < i; j = j + 1)
        {   if (i%j == 0)
            {   primes.pop_back();
                j = n + 1;
            }
        }
    }
Code:
        for(int j = 2; j <= (int)sqrt(static_cast<float>(n)) && j < i; j = j + 1)
wouldnt that line call for a static cast and a sqroot to check the value on each loop, or would it register the info??
creating a variable and giving it this value outside the loop wouldn't hurt, then use the variable in the evaluation.

Last edited by dmail; 10-26-2005 at 12:20 PM.
 
Old 10-26-2005, 03:43 PM   #17
lmvent
LQ Newbie
 
Registered: Sep 2005
Posts: 24

Original Poster
Rep: Reputation: 15
Code:
#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

int main(void)
{   cout << "Input the largest positive integer to check: ";
    unsigned int maxN;
    cin >> maxN;
    int n = (int)sqrt(static_cast<float>(maxN));
    int k = (int)sqrt(static_cast<float>(n));
    vector<int>primes;
    if(maxN > 1)
    {   primes.push_back(2);
    }
    for(int i = 3; i <= n ; i = i + 2)
    {   primes.push_back(i);
        for(int j = 2; j < i && j <= k; j = j + 1)
        {   if (i%j == 0)
            {   primes.pop_back();
                j = i + 1;
            }
        }
    }
    if(n%2 == 0)
    {   int p = n + 1;
    }
    else
    {   int p = n;
    }
    for(int i = p; i <= maxN; i = i + 2)
    {   primes.push_back(i);
        for(int j = 0; j <= primes.size() - 1; j = j + 1)
        {   if(i%primes[j] == 0)
            {   primes.pop_back();
                j = n + 1;
            }
        }
    }
    //for(int j = 0; j < primes.size(); j = j + 1)
    //{   cout << primes[j] << " ";
    //}
    cout << "\n\nThere are " << primes.size() << " prime numbers <= " << maxN << "\n";
    return 0;
}
Okay, this is what I have now. I took into account the fact that I only need to check odd numbers to see if they are prime. I checked to see if only adding the number to the vector after it has been proven prime would save time, but I don't know exactly how to do that. Here is the top half of the above code with the only way I could figure to only add the number after it is proven prime.

Code:
int main(void)
{   cout << "Input the largest positive integer to check: ";
    unsigned int maxN;
    cin >> maxN;
    int n = (int)sqrt(static_cast<float>(maxN));
    int k = (int)sqrt(static_cast<float>(n));
    vector<int>primes;
    if(maxN > 1)
    {   primes.push_back(2);
    }
    int r;
    for(int i = 3; i <= n ; i = i + 2)
    {   r = 0;
        for(int j = 2; j < i && j <= k; j = j + 1)
        {   if (i%j != 0)
            {   r = r + 1;
            }
            if(r == i - 2)
            {   primes.push_back(i);
            }
        }
    }
}
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
How to increase speed of firefox!!!!!!! Lier Linux - Software 3 08-16-2005 05:00 PM
how to increase booting speed linuxaddict Linux - General 4 11-17-2003 12:17 PM
SPEED : How to increase? isone Linux - Newbie 1 10-29-2003 04:29 AM
increase hd speed saavik Linux - Hardware 3 07-23-2003 10:54 AM
Comcast speed increase tarballedtux Linux - Networking 0 03-01-2002 11:45 AM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 08:52 AM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Open Source Consulting | Domain Registration