| Cloud Sexico. July 15 2010 21:35. Posts 5603 | Profile Blog # |
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;
}
Last edit: 2010-07-15 21:39:24 |
| | BlueLaguna on West, msg for game. | |
|
|
| Adeny Norway. July 15 2010 22:41. Posts 1230 | Profile Blog # |
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.Last edit: 2010-07-16 00:54:14 |
|
|
| catamorphist United States. July 15 2010 23:22. Posts 297 | Profile # |
| The above poster is right on except that 32 bits is good up to 2 billion, not 2 million. |
| | http://us.battle.net/sc2/en/profile/281144/1/catamorphist/ |
|
|
| Adeny Norway. July 16 2010 00:53. Posts 1230 | Profile Blog # |
| Oops, my bad. Thanks for the correction. |
|
|
| EpiK Korea (South). July 16 2010 07:38. Posts 4679 | Profile Blog # |
Poll: Which language do you use the most often? C++ (10) 24% C# (9) 21% Java (8) 19% C (6) 14% 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% 42 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. Last edit: 2010-07-16 08:07:18 |
|
|
| UdderChaos July 16 2010 07:49. Posts 513 | Profile Blog # |
| lol VB isn't a real language, it's like the mac of the programming languages. |
| | Nunquam iens addo vos sursum |
|
|
| dimfish United States. July 16 2010 07:56. Posts 661 | Profile Blog # |
| 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. |
|
|
| Count9 China. July 16 2010 08:05. Posts 3681 | Profile Blog # |
| 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. |
|
|
| mmp United States. July 16 2010 08:10. Posts 2126 | Profile Blog # |
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_primeLast edit: 2010-07-16 08:16:55 |
| | I (λ (foo) (and (<3 foo) ( T_T foo) (RAGE foo) )) Starcraft | |
|
|
| Gogleion United States. July 16 2010 08:13. Posts 533 | Profile Blog # |
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. Last edit: 2010-07-16 08:16:12 |
| |
|
 TanGeng China. July 16 2010 08:17. Posts 4395 | Profile # |
| C because of Linux driver development. |
| | Get Strong at Doublethink! 毛毛鸭 小明 木 加油！！ | |
|
|
| Craton United States. July 16 2010 08:52. Posts 10146 | Profile Blog # |
| 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. Last edit: 2010-07-16 08:52:18 |
| | jeongmal kkeutnangeongayo (mari eoptneyo) eonjena geuraetjyo || LoL 2350+ Jungler || KPop: http://cratonz.minus.com/uploads |
|
|
| catamorphist United States. July 16 2010 08:58. Posts 297 | Profile # |
| 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.) Last edit: 2010-07-16 09:00:00 |
| | http://us.battle.net/sc2/en/profile/281144/1/catamorphist/ |
|
|
| RoTaNiMoD United States. July 16 2010 09:09. Posts 558 | Profile Blog # |
| 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. |
|
|
| Craton United States. July 16 2010 09:22. Posts 10146 | Profile Blog # |
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.2571679Last edit: 2010-07-16 09:57:21 |
| | jeongmal kkeutnangeongayo (mari eoptneyo) eonjena geuraetjyo || LoL 2350+ Jungler || KPop: http://cratonz.minus.com/uploads |
|
|
| SoLaR[i.C] United States. July 16 2010 09:27. Posts 2969 | Profile Blog # |
| Anybody have a suggestion for a FORTRAN compiler? |
|
|
| TanGeng China. July 16 2010 09:29. Posts 4395 | Profile # |
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.Last edit: 2010-07-16 09:33:12 |
| | Get Strong at Doublethink! 毛毛鸭 小明 木 加油！！ | |
|
|
| RoTaNiMoD United States. July 16 2010 09:34. Posts 558 | Profile Blog # |
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. |
|
|
| lastkarrde New Zealand. July 16 2010 09:42. Posts 66 | Profile # |
Python Hwaiting!
Pypy is getting faster and more featureful by the day, damn awesome. |
| |
|
| Craton United States. July 16 2010 09:48. Posts 10146 | Profile Blog # |
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;
}
Last edit: 2010-07-16 10:03:36 |
| | jeongmal kkeutnangeongayo (mari eoptneyo) eonjena geuraetjyo || LoL 2350+ Jungler || KPop: http://cratonz.minus.com/uploads |
|
|
| Prev 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 100 200 293 294 295 296 297 298 299 300 301 302 303 Next |
|
