|
Thread Rules
1. This is not a "do my homework for me" thread. If you have specific questions, ask, but don't post an assignment or homework problem and expect an exact solution.
2. No recruiting for your cockamamie projects (you won't replace facebook with 3 dudes you found on the internet and $20)
3. If you can't articulate why a language is bad, don't start slinging shit about it. Just remember that nothing is worse than making CSS IE6 compatible.
4. Use [code] tags to format code blocks. |
Hey, could someone help me with problem 10? (find the sum of all primes below two million).
My code works just fine for small numbers but when it goes above a certain number it just displays a bunch of crap. I wanna know if I'm declaring my types wrong or if there's something else wrong.
+ Show Spoiler +The function primo checks if it's a prime. If it's a prime it returns a 1 and the main function sums it to 17 (I skip 2, 3, 5 and 7). All prime numbers apart from 2 and 3 are of the form 6*i +/- 1, and to check if it's a prime you don't need to go above the sqrt of the number.
#include <stdio.h>
#include <math.h>
#define MAX 2000000
int primo(int);
int main(void)
{
int i;
long int suma = 17;
for (i= 2; i * 6 + 1 < MAX; i++) {
if (primo((i * 6) + 1) == 1)
suma += ((i * 6) + 1);
}
for (i = 2; i * 6 - 1 < MAX; i++) {
if (primo((i * 6) - 1) == 1)
suma += ((i * 6) - 1);
}
printf("%d", suma);
return 0;
}
int primo(int num)
{
int i;
float j;
if (num % 2 == 0)
return 0;
if (num % 3 == 0)
return 0;
j = sqrt(num);
for (i = 1; i * 6 + 1 <= j; i++) {
if (num % (i * 6 + 1) == 0)
return 0;
}
for (i = 1; i * 6 - 1 <= j; i++) {
if (num % (i * 6 - 1) == 0)
return 0;
}
return 1;
}
|
I can't remember the exact value, but an int can only store so much, and it's around 2 billion somewhere. Try changing your ints to unsigned int. What this does, is it changes your number range from -2 billion to +2 billion, to 0 to 4 billion instead.
Normally your int has 1 bit that's designated to tell if it's a positive or negative number, so you can only store up to 2^31 (which makes 32 bit total). With unsigned, you get the range of 2^32. I don't know if that's clear or not. There are also some other datatypes that can store larger numbers, but if you want REALLY large numbers in C/++, you're going to need a custom class/library, like GMP Big Num.
Oh, and for optimizing primes, you should store the primes in an array, and loop through it. You also only need to check upwards to the square root of n. Oh in your for loops, you can use whatever you like, so starting at 3 and doing i += 2 is twice as (approx) as i++, because you know all even numbers are divisible by 2.
Edit: Billion, not Million.
|
The above poster is right on except that 32 bits is good up to 2 billion, not 2 million.
|
Oops, my bad. Thanks for the correction.
|
Poll: Which language do you use the most often? C++ (10) 23% C# (9) 21% Java (8) 19% C (7) 16% Python (5) 12% Perl (1) 2% Ruby (1) 2% Delphi (1) 2% Other (please specify) (1) 2% PHP (0) 0% Visual Basic (0) 0% JavaScript (0) 0% 43 total votes Your vote: Which language do you use the most often? (Vote): C
(Vote): Java
(Vote): C#
(Vote): C++
(Vote): PHP
(Vote): Visual Basic
(Vote): Python
(Vote): Perl
(Vote): JavaScript
(Vote): Ruby
(Vote): Delphi
(Vote): Other (please specify)
C# mostly for me. I've been using a lot of python too lately for a school project I'm doing with the panda3d engine.
|
lol VB isn't a real language, it's like the mac of the programming languages.
|
I voted for C++, but really I mostly use C and only C++ when C is decidedly inconvenient (like not letting me declare local variables right before I want to use them). I'm really curious to see how this poll turns out. Maybe the poll should be what you use the most for work projects and one for what you use on your own time.
|
Perl all the way, mostly because I don't want to be able to read my programs when I'm done so I don't have to debug. I use tcl a lot too.
|
On July 15 2010 21:35 Cloud wrote:Hey, could someone help me with problem 10? (find the sum of all primes below two million). My code works just fine for small numbers but when it goes above a certain number it just displays a bunch of crap. I wanna know if I'm declaring my types wrong or if there's something else wrong. + Show Spoiler +The function primo checks if it's a prime. If it's a prime it returns a 1 and the main function sums it to 17 (I skip 2, 3, 5 and 7). All prime numbers apart from 2 and 3 are of the form 6*i +/- 1, and to check if it's a prime you don't need to go above the sqrt of the number.
#include <stdio.h>
#include <math.h>
#define MAX 2000000
int primo(int);
int main(void)
{
int i;
long int suma = 17;
for (i= 2; i * 6 + 1 < MAX; i++) {
if (primo((i * 6) + 1) == 1)
suma += ((i * 6) + 1);
}
for (i = 2; i * 6 - 1 < MAX; i++) {
if (primo((i * 6) - 1) == 1)
suma += ((i * 6) - 1);
}
printf("%d", suma);
return 0;
}
int primo(int num)
{
int i;
float j;
if (num % 2 == 0)
return 0;
if (num % 3 == 0)
return 0;
j = sqrt(num);
for (i = 1; i * 6 + 1 <= j; i++) {
if (num % (i * 6 + 1) == 0)
return 0;
}
for (i = 1; i * 6 - 1 <= j; i++) {
if (num % (i * 6 - 1) == 0)
return 0;
}
return 1;
}
When doing primality calculations you want to use bigint libraries to avoid overflowing (an array of ints or a string/char* representation - makes things a little clumsy but saves a real headache) - you can also use Fermat's Little Theorem to test primality in constant time - and maintain a database of Carmichael numbers for small n. Most bigint libraries should already have probable primality implemented for you, although it's very easy to write yourself. 
Source: http://en.wikipedia.org/wiki/Probable_prime
|
Java fighting! Its gotten seriously good over the past 5 years and is now extremely powerful, and not a 'toy' language that I hear a lot of people call it. I'm saddened when I see C# is in first... D:
I use PHP a lot too, but that's just because of how I do web development. I don't necessarily like PHP as a language though.
COBOL isn't on the list, it is mostly outdated, but professional COBOL programmers make serious money since its really good for databases and not a lot of people are good at it.
Also Pascal isn't on there. I'm pretty sure either bwchart or chaoslauncher was made in pascal. Also missing is J, a relatively obscure but powerful language in the hands of people that know it. Also QBasic, ASP.net, MySQL, HTML, and XML/AJAX (I know JavaScript is on there already) are missing to name a few more.
EDIT: I'm really happy to see eulers on here. If anyone else is interested I could probably make a thread discussing them.
|
Sanya12364 Posts
C because of Linux driver development.
|
C# with ASP.NET for all my work right now and a lot of VB.NET for school, but I think I'm done with VB.NET here on out.
|
C#, F#, T-SQL at work, and mostly Clojure at home. (For a long time before six months ago I would have said mostly PLT Scheme at home, but Clojure really 0wns.)
|
C++ all the way. Complete memory control laughs in the face of your puny garbage collection. I am interested to see how this poll will turn out and am happy with the setup. The main languages are all there with enough room for a decent amount of less prominent languages too. MySQL/HTML/XML, though certainly intrinsic parts of development processes, aren't actually programming languages and thus are good to be left off.
|
We could make a Euler's blog rather than it's own thread, but I'm down for either.
Got the prime one right on first try, but hella slow. (Visual C#)
Time: 00:04:35.2571679
|
Anybody have a suggestion for a FORTRAN compiler?
|
Sanya12364 Posts
On July 16 2010 09:09 RoTaNiMoD wrote:
C++ all the way. Complete memory control laughs in the face of your puny garbage collection. I am interested to see how this poll will turn out and am happy with the setup. The main languages are all there with enough room for a decent amount of less prominent languages too. MySQL/HTML/XML, though certainly intrinsic parts of development processes, aren't actually programming languages and thus are good to be left off.
this
There is more code to write though. I know a lot of languages and use them all depending on existing code base, performance requirements, and time constraints.
The argument that you can bang something out really really fast, is ultra portable, or has the best library support is a strong selling point for the languages with automatic cleanup.
|
On July 15 2010 21:35 Cloud wrote:Hey, could someone help me with problem 10? (find the sum of all primes below two million). My code works just fine for small numbers but when it goes above a certain number it just displays a bunch of crap. I wanna know if I'm declaring my types wrong or if there's something else wrong. + Show Spoiler +The function primo checks if it's a prime. If it's a prime it returns a 1 and the main function sums it to 17 (I skip 2, 3, 5 and 7). All prime numbers apart from 2 and 3 are of the form 6*i +/- 1, and to check if it's a prime you don't need to go above the sqrt of the number.
#include <stdio.h>
#include <math.h>
#define MAX 2000000
int primo(int);
int main(void)
{
int i;
long int suma = 17;
for (i= 2; i * 6 + 1 < MAX; i++) {
if (primo((i * 6) + 1) == 1)
suma += ((i * 6) + 1);
}
for (i = 2; i * 6 - 1 < MAX; i++) {
if (primo((i * 6) - 1) == 1)
suma += ((i * 6) - 1);
}
printf("%d", suma);
return 0;
}
int primo(int num)
{
int i;
float j;
if (num % 2 == 0)
return 0;
if (num % 3 == 0)
return 0;
j = sqrt(num);
for (i = 1; i * 6 + 1 <= j; i++) {
if (num % (i * 6 + 1) == 0)
return 0;
}
for (i = 1; i * 6 - 1 <= j; i++) {
if (num % (i * 6 - 1) == 0)
return 0;
}
return 1;
}
Cloud: good start, but to achieve speed-efficiency, you are going to need to make some changes. First, your primeness test. The i*6+/-1 idea is near-optimal for small n, but as n grows there becomes more and more overlap between tests (for example testing 4*6+1 -- 25 -- is redundant when you also test for 1*6-1 -- 5). Instead, store all your primes in an array of some sort and only test n for divisibility by prime numbers up to sqrt(n).
Second, your for loops could use some optimization. Generally this is no big deal, but in programs like this, where you spend an extreme amount of time looping, optimizing your statements can provide huge speed boosts. Every time you compute ( i * 6 +/- 1 ), two unnecessary evaluations are made (multiplication by 6 and addition/subtraction of 1). Simply having a variable for that value would save you several evaluations per loop-cycle. When each cycle is only 15 or so evalutions to begin with, that's huge.
|
Python Hwaiting!
Pypy is getting faster and more featureful by the day, damn awesome.
|
aha wow what a difference that makes rotan
+ Show Spoiler +The sqrt part. private void btnGo_Click(object sender, EventArgs e)
{
Stopwatch stopWatch = new Stopwatch();
stopWatch.Start();
Int64 Total = 0;
List<int> list = new List<int>();
Boolean isPrime = true;
for (int i = 2; i <= 2000000; i++)
{
isPrime = true;
foreach (int j in list)
{
if (i % j == 0)
{
//Not a prime
isPrime = false;
break;
}
//****** Change Start ******
if (j > Math.Sqrt(i))
break;
//****** Change End ******
} //j
if (isPrime)
{
Total += i;
list.Add(i);
}
} //i
stopWatch.Stop();
txtEuler.Text = Total.ToString() + " -- Time: " + stopWatch.Elapsed;
}
Got mine down to:
Time: 00:00:01.1228236
Bolded my change. Or, I would have but you can't have bold tags in code. Added comments.
Time: 00:00:00.3553445 for #7, 10001st prime. Kinda pointless once you've got the other one done, though =/.
+ Show Spoiler +
private void btnPrime10001_Click(object sender, EventArgs e)
{
Stopwatch stopWatch = new Stopwatch();
stopWatch.Start();
Int64 Total = 0;
List<int> list = new List<int>();
Boolean isPrime = true;
int i = 2;
while (list.Count() != 10001)
{
isPrime = true;
foreach (int j in list)
{
if (i % j == 0)
{
//Not a prime
isPrime = false;
break;
}
if (j > Math.Sqrt(i))
{
break;
}
} //j
if (isPrime)
{
list.Add(i);
}
i++;
} //i
stopWatch.Stop();
txtEuler.Text = list[10000].ToString() + " -- Time: " + stopWatch.Elapsed;
}
|
|
|
|
|
|
EPT
